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 NPComplete
We know that a problem is in class NPComplete if: it is in NP and it is NP Hard.
Theorem:
Clique problem is NPcomplete.
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 NPhard.
We know that a problem is NPHard, 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 3CNFSAT problem. Then, if we can reduce 3CNFSAT problem to clique problem in polynomial time, we can say that clique is NPhard.
We need to reduce 3CNFSAT problem to clique problem.
Consider a 3CNF 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 3CNFSAT 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 3CNF gives true for a=0, b=0, c=1.
Thus the given 3CNFSAT problem is reduced to clique problem. This means clique problem is NPhard.
In step 1, we proved that clique is in NP.
In step 2, we proved that clique is NPhard.
So, clique is an NPcomplete problem.
18 videos56 docs44 tests

1. What is the clique problem in computer science engineering? 
2. How is the complexity of the clique problem determined? 
3. Can the clique problem be solved using brute force? 
4. Are there any approximation algorithms for the clique problem? 
5. What are some applications of the clique problem in computer science engineering? 
18 videos56 docs44 tests


Explore Courses for Computer Science Engineering (CSE) exam
