Here is an exercise my friend proposed to me:

Show that the maximum clique problem polynomial time reduces to the maximum independent set problem.

Here is my attempt at solving it:

It is known that the maximum independent set problem and the maximum clique problem are polynomially equivalent.

Proof of statement:
-We know that a maximum independent set is simply the largest maximal independent set, where an independent set is a set of non-adjacent nodes in a graph.

-We know that the maximum clique is defined as the largest clique, which is a fully connected subgraph.

-The complement of a clique, then, is an independent set, and vice versa. Thus, finding the maximum clique is equivalent to finding the maximum independent set, and vice versa.

So here's where I'm running into a wall... I can demonstrate equivalency between the two problems, but I can't demonstrate reduction from the Clique problem to the Independent set problem... It seems to me that they have the same complexity, so

Maximum Independent Set Problem ~ $\Theta$(Maximum Clique Problem)

Can anyone weigh in on this problem? I feel like I'm overlooking something important.

Thank you very much!

  • 2
    $\begingroup$ hint: consider the complement graph. $\endgroup$ – Kaveh May 7 '12 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.