The document Clique Problem Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**Part V. Clique Problem****9 Clique Problem****Clique**

Let we are given a graph with a number of vertices. A clique is a subset of vertices, such that an edge is present between every pair of vertices.

Consider the following graph:

In the above graph, a clique is {u,v,x,y}. The size of this clique is 4.

A clique is a subgraph of the above graph which is shown below:

The above set is a clique, because uv, ux, uy, vx, vy, xy are edges in the given graph.

**Clique Problem**

Clique problem is to check whether a clique of size k is present in the graph.

**Clique Problem is NP-Complete**

We know that a problem is in class NP-Complete if: it is in NP and it is NP Hard.**Theorem:**

Clique problem is NP-complete.

**Proof:**

Step 1: Prove that clique problem is in class NP.

A set with n elements has 2^{n }possible subsets. Then a graph with n vertices has 2^{n} possible subgraphs. So an algorithm needs to check whether any one of these subgraphs form a clique. It has worst case time complexity Θ(2^{n}). (not polynomial time, but exponential time). Let we are given a graph and a ’certificate’ telling that a subset of vertices form a clique. An algorithm can verify this in polynomila time. So clique problem is in class NP.

Step 2: Prove that clique problem is NP-hard.

We know that a problem is NP-Hard, if every problem in NP can be reduced to this problem in polynomial time. The approach we used is as follows:

In the previous section, we already proved that all NP problems can be reduced to SAT. Then, again we found that SAT problem can be reduced to 3-CNF-SAT problem. Then, if we can reduce 3-CNF-SAT problem to clique problem in polynomial time, we can say that clique is NP-hard.

We need to reduce 3-CNF-SAT problem to clique problem.

Consider a 3-CNF boolean formula given below:

(a ∪ ¬b ∪ ¬c) ∩ (¬a ∪ b ∪ c) ∩ (a ∪ b ∪ c)

A graph is produced from the above formula as:

The graph is produced as follows:

Every vertex in a clause is connected to every other vertex in another clause. But a vertex x should not be connected to vertex __x__.

This graph corresponding to 3-CNF-SAT has a solution if the corresponding vertices form a clique.

In the above graph, vertices ¬b of C_{1}, ¬a of C_{2}, c of C_{3} form a clique.

In the above clique, C_{1 }has the vertex ¬b. So put b=0.

C_{2} has the vertex ¬a. So put a=0.

C_{3} has the vertex c. So put c=1.

Thus a satisfying assignment to the given boolean formula is a=0, b=0, c=1.

Consider the given boolean formula,

(a ∪ ¬b ∪ ¬c) ∩ (¬a ∪ b ∪ c) ∩ (a ∪ b ∪ c)

Put a=0, b=0, c=1, we get,

(0 ∪ ¬0 ∪ ¬1) ∩ (¬0 ∪ 0 ∪ 1) ∩ (0 ∪ 0 ∪ 1)

=(0 ∪ 1 ∪ 0) ∩ (1 ∪ 0 ∪ 1) ∩ (0 ∪ 0 ∪ 1)=1 ∩ 1 ∩ 1=1

Thus the given formula in 3-CNF gives true for a=0, b=0, c=1.

Thus the given 3-CNF-SAT problem is reduced to clique problem. This means clique problem is NP-hard.

In step 1, we proved that clique is in NP.

In step 2, we proved that clique is NP-hard.

So, clique is an NP-complete problem.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

36 videos|39 docs|39 tests