Clique Problem | Theory of Computation - Computer Science Engineering (CSE) PDF Download

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ⁿ possible subsets. Then a graph with n vertices has 2ⁿ possible subgraphs. So an algorithm needs to check whether any one of these subgraphs form a clique. It has worst case time complexity Θ(2ⁿ). (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₁, ¬a of C₂, c of C₃ form a clique.

In the above clique, C₁ has the vertex ¬b. So put b=0.
C₂ has the vertex ¬a. So put a=0.
C₃ 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.