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

Problem Detail: 

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.

Asked By : Toralf Westström

Answered By : Greg

You have it backwards- you have to reduce a known NP-complete problem to the thing that you want to show is NP-hard. If you were to reduce Vertex-Cover to Stable-Set, you would be saying that Stable-Set is at least as hard as Vertex-Cover... but Vertex-Cover could still theoretically be polynomial.

Since this seems like a homework problem, I don't want to actually give the solution here. What you need to do is find a way of transforming the Stable-Set problem into the Vertex-Cover problem. That way, any solution to Vertex-Cover would be a solution to Stable-Set, so VC is at least as hard as SS. After that, you need to show that VC (note that you need to work with the decision version of VC and SS, which asks does there exists a VC/SS of size k) is in NP by showing that given a witness, you can check if it's correct or not.

Solutions to both problems are sets of nodes in a graph. If there's a VC of size k, that means that all edges have at least one node touching them. If there's a SS of size k, that means no edge has two nodes touching them. I'd suggest drawing out some graphs, finding the VC and SS of both of them, and seeing if there's a relationship between the two sets, as well as the size of each set and the number of nodes in the graph. While I haven't worked out a proof, I don't think you need to do a transformation on the graph itself (like drawing in new nodes/edges) in this case. However, for some problems, you might need to.

Here is a handout on NP-completeness reductions, which might help you. I suggest reading some reductions to get a handle on it.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11954