patternModerate
Reducing Clique to Independent Set
Viewed 0 times
setcliquereducingindependent
Problem
The Clique problem takes a graph $G = (V,E)$ and an integer $k$ and asks if $G$ contains a clique of size $k$. (A clique is a set of vertices such that every pair of vertices in the set is adjacent.) The Independent-Set problem takes a graph $G’ = (V’,E’)$ and an integer $k’$ and asks if $G’$ contains an independent set of size $k’$. (An independent set is a set of vertices such that no pair of vertices in the set is adjacent.)
-
Give a polynomial time algorithm that, given a graph $G$ and an integer $k$ produces a graph $G’$ and an integer $k’$ such that $G$ has a clique of size $k$ if and only if $G’$ has an independent set of size $k’$. Justify your answer.
-
Use 1. to prove that the Independent-Set problem is NP-Complete given that the Clique problem is NP-Complete.
-
Give a polynomial time algorithm that, given a graph $G$ and an integer $k$ produces a graph $G’$ and an integer $k’$ such that $G$ has a clique of size $k$ if and only if $G’$ has an independent set of size $k’$. Justify your answer.
-
Use 1. to prove that the Independent-Set problem is NP-Complete given that the Clique problem is NP-Complete.
Solution
The trick is to realize that if a graph has a clique of size $k$, the inverse graph has an independent set of size $k$. A clique of size $k$ means that $k$ nodes all have edges in between them. In the inverse graph these $k$ nodes are not (directly) connected and can be used to create an independent set of size $k$
Hence, the polynomial time algorithm you are looking for is merely the one that inverts the graph.
You will find a youtube explanation here.
I suspect that if you try to draw some very simple graphs with cliques and the inverses of said graphs you will realize why this is true.
As for (2), you need to show that an algorithm to the independent set problem can be used to solve the clique problem. Furthermore you need to show that using the solution to the independent set problem can be used to find the solution to the clique problem in polynomial time. This proves the following:
You can now reduce the clique problem to independent set. As all problems in NP can be reduced to the clique problem (the definition of clique being in NPC) all problems in NP can be reduced to independent set too and so it is in NPC. And since you reduced clique to independent set in polynomial time it cannot be harder than the clique problem either.
So (2) is equivalent to the following: If you were given a polynomial time algorithm for the independent set problem, how would you use it to find out whether a graph had a clique of size $k$?
Hence, the polynomial time algorithm you are looking for is merely the one that inverts the graph.
You will find a youtube explanation here.
I suspect that if you try to draw some very simple graphs with cliques and the inverses of said graphs you will realize why this is true.
As for (2), you need to show that an algorithm to the independent set problem can be used to solve the clique problem. Furthermore you need to show that using the solution to the independent set problem can be used to find the solution to the clique problem in polynomial time. This proves the following:
You can now reduce the clique problem to independent set. As all problems in NP can be reduced to the clique problem (the definition of clique being in NPC) all problems in NP can be reduced to independent set too and so it is in NPC. And since you reduced clique to independent set in polynomial time it cannot be harder than the clique problem either.
So (2) is equivalent to the following: If you were given a polynomial time algorithm for the independent set problem, how would you use it to find out whether a graph had a clique of size $k$?
Context
StackExchange Computer Science Q#7120, answer score: 13
Revisions (0)
No revisions yet.