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!