# Show that Vertex-Cover is NP-complete, using Stable-Set

My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too.

My approach: i know, Stable-Set is NP-complete, and all Problems that are NP-complete can be reduced to each other. If i could solve one NP-complete problem, i might be able to solve all NP-complete problems. It should be possible to create a function with polynomial complexity to reduce Vertex-Cover to Stable-Set. At least, this was, what my Professor told.

Now all i have to do, is to find this polynomial function, in order to Show that Vertex-Cover is NP-complete. But here is where i am stuck.. so i need some advice how to build such functions.

• So, after reading and thinking about and after drawing dozends of graphs i think i maybe found the answer. If $G(V,E)$ is a graph, and $A$ is a Stable Set with, $A \subseteq$ V, than is $V-A=B$ with $B$ being a Vertex Cover for $G(V,E)$... right? So my function $f(x)$, that i need for polynomial reduction could look like that: $f(x)=V-x$ with $x \in \{soulutions\ of\ Stable\ Set\ for\ graph\ G\}$ ? May 15, 2013 at 13:21