Reduction of NP problems

[lukatmyshu]

I have a final tomorrow and I am having a huge problem solving some of these NP reduction problems. Anyone whose any good at this stuff want to reduce it for me? The problem is
Given a graph G = (V,E) A 2-Dominating Set is a set S such that every vertex is either in S or reachable via 1 or 2 edges to some vertex in S. Prove that this problem is NP-Complete via reduction. You may assume that Independent Set is NP-Complete.
I am guessing that I should reduce this to Independent Set (which asks to find a set I of graph (V,E) such that no two vertices in I are adjacent) ... but I can't see how they're related. I also wonder if I need to look at minimum vertex cover (which states asks to find a set V for a graph (V,E) such that for all edges (u,v) in E either u is in V or v is in V). Anybody smart awake?

 

[gopunk]

bah we covered a little bit of this in my data structures class, but not that in depth.. and my brain is fried... sorry. bump for you!

 

[tom3]

Given a graph G = (V,E) A 2-Dominating Set is a set S such that every vertex is either in S or reachable via 1 or 2 edges to some vertex in S. Prove that this problem is NP-Complete via reduction. You may assume that Independent Set is NP-Complete.

If that is all is given in the problem, chances are Independent Set is sufficient in deriving the reduction.

One would want to reduce from the problem known to be NPC to the new problem in order to establish the NPCness of the new problem. So in this case, you would want to give a polynomial-time many one reduction from Ind. Set. to the 2-Dom. Set problem.

Is this a practice problem for the final?
let me think about it for a bit before i reply again with hopefully more help

 

[tom3]

I cant really think of any useful insight, but I believe reduction from vertex cover would work. Vertex cover is also NPC.

Sorry I cant give you more help.. just remember that in proving something NP complete, you have to show both of the following conditions are satisfied:

1) That the language is in NP. (this is often trivial, just either show that a nondeterministic Turing machine decides it, or show that it has a polynomial time verifier)

2) That the language is NP-hard. (here is where the reduction from a known NPC problem takes place)

In the reduction, remember that you must show the reduction is in polynomial time, and also you must show that it works both ways. The reduction function f should be such that "for all w, w is in A if and only if f(w) in B". Since it's an iff, you have to show that w in A -> f(w) in B, and that f(w) in B -> w in A.

 

[lukatmyshu]

Haven't really been able to figure anything more on this problem. My only insight, in terms of using vertex cover, is that the 2-Dominating Set has to be a subset of Vertex Cover. So let us assume that instead of trying to find a reduction from VC to 2DS, we can say this : let us use 2DS = C to approximate VC. Then for all (u,v) in E if u is not in C add u, if v is not in E add C. Since 2DS gave us a non-zero subset of VC, and our algorithm ensured that we have a valid vertex cover, we can speculate on |C|. Since 2DS returned a non-zero subset, and our approximation algorithm gave us a result that was at most twice as large as the correct result, this means that we have an upper bound on |C| as 2c*-1, where c* is an optimal solution. Since the current best approximation for VC is 2c*, this is not possible ... unless P=NP.
Doesn't really prove that 2DS is NPC, but at least it shows ... something.