5
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ This is obviously a homework problem. What have you tried so far, and where did you get stuck? $\endgroup$
    – adrianN
    Dec 3, 2012 at 10:48
  • 3
    $\begingroup$ Have you really thought about the definition of a Clique? $\endgroup$
    – Luke Mathieson
    Dec 3, 2012 at 11:39
  • $\begingroup$ Actually no .iam trying to start but i cant . $\endgroup$
    – mona
    Dec 3, 2012 at 15:40
  • $\begingroup$ This is a common problem so I am surprised it has not been asked before. $\endgroup$
    – The Unfun Cat
    Dec 3, 2012 at 18:47

1 Answer 1

Reset to default
13
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ If any of you brainiacs can think of a better/nicer explanation of the second last paragraph I would appreciate an edit. $\endgroup$
    – The Unfun Cat
    Dec 3, 2012 at 18:51
  • 2
    $\begingroup$ A very good explanation: hananayad.com/teaching/syde423/IndependentSet.pdf $\endgroup$
    – The Unfun Cat
    Dec 3, 2012 at 18:54
  • $\begingroup$ 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. $\endgroup$
    – KKS
    Mar 30, 2016 at 4:41
  • $\begingroup$ "Inverse graph" - perhaps "complementing graph" or "complementary graph" $\endgroup$
    – einpoklum
    Feb 22, 2019 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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