Clique Problem Computer Science Engineering (CSE) Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : Clique Problem Computer Science Engineering (CSE) Notes | EduRev

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:
Clique Problem Computer Science Engineering (CSE) Notes | EduRev
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:
Clique Problem Computer Science Engineering (CSE) Notes | EduRev
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 2possible 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.
Clique Problem Computer Science Engineering (CSE) Notes | EduRev
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:
Clique Problem Computer Science Engineering (CSE) Notes | EduRev
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.
Clique Problem Computer Science Engineering (CSE) Notes | EduRev
In the above clique, Chas 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.

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

Related Searches

shortcuts and tricks

,

MCQs

,

mock tests for examination

,

Clique Problem Computer Science Engineering (CSE) Notes | EduRev

,

Extra Questions

,

Clique Problem Computer Science Engineering (CSE) Notes | EduRev

,

Viva Questions

,

Summary

,

video lectures

,

ppt

,

study material

,

Exam

,

Sample Paper

,

past year papers

,

Objective type Questions

,

pdf

,

Semester Notes

,

Free

,

Previous Year Questions with Solutions

,

Important questions

,

Clique Problem Computer Science Engineering (CSE) Notes | EduRev

,

practice quizzes

;