# Reducing Clique to Independent Set

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.)

1. 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.

2. Use 1. to prove that the Independent-Set problem is NP-Complete given that the Clique problem is NP-Complete.

• This is obviously a homework problem. What have you tried so far, and where did you get stuck? Dec 3 '12 at 10:48
• Have you really thought about the definition of a Clique? Dec 3 '12 at 11:39
• Actually no .iam trying to start but i cant .
– mona
Dec 3 '12 at 15:40
• This is a common problem so I am surprised it has not been asked before. Dec 3 '12 at 18:47

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$?

• If any of you brainiacs can think of a better/nicer explanation of the second last paragraph I would appreciate an edit. Dec 3 '12 at 18:51
• A very good explanation: hananayad.com/teaching/syde423/IndependentSet.pdf Dec 3 '12 at 18:54
• See Garey Johnson's book "Computers and Intractability". It in fact contains polynomial reductions to each other of Vertex Cover, Maximum Independent Set and Maximum Clique problems. See Lemma 3.1 page 54 of the book. It is given as an exercise but the lemma formulation makes it easy to give a polynomial reduction a give the proof.
– KKS
Mar 30 '16 at 4:41
• "Inverse graph" - perhaps "complementing graph" or "complementary graph" Feb 22 '19 at 18:27