Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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.

share|improve this question
6  
This is obviously a homework problem. What have you tried so far, and where did you get stuck? –  adrianN Dec 3 '12 at 10:48
3  
Have you really thought about the definition of a Clique? –  Luke Mathieson 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. –  The Unfun Cat Dec 3 '12 at 18:47
add comment

1 Answer

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

share|improve this answer
    
If any of you brainiacs can think of a better/nicer explanation of the second last paragraph I would appreciate an edit. –  The Unfun Cat Dec 3 '12 at 18:51
1  
A very good explanation: hananayad.com/teaching/syde423/IndependentSet.pdf –  The Unfun Cat Dec 3 '12 at 18:54
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.