Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
hint: consider the complement graph. –  Kaveh May 7 '12 at 7:56

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.