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 2n possible subsets. Then a graph with n vertices has 2n possible subgraphs. So an algorithm needs to check whether any one of these subgraphs form a clique. It has worst case time complexity Θ(2n). (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 C1, ¬a of C2, c of C3 form a clique.
In the above clique, C1 has the vertex ¬b. So put b=0.
C2 has the vertex ¬a. So put a=0.
C3 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.
18 videos|69 docs|44 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? |
|
Explore Courses for Computer Science Engineering (CSE) exam
|