2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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\}$ ? $\endgroup$
    – Toralf Westström
    Commented May 15, 2013 at 13:21
  • $\begingroup$ Yup, pretty sure that's most of the answer. A proof would show the if and only if nature. One thing you still need to think about is how the sizes of your answers relate. $\endgroup$
    – Greg
    Commented May 15, 2013 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.