Proof that Dominating Set is NP-Complete

here is the question. I am wondering if there is a clear and efficient proof:

Vertex Cover: input undirected G, integer k > 0. Is there a 开发者_StackOverflowsubset of vertices S, |S|<=k, that covers all edges?

Dominating Set: input undirected G, integer k > 0. Is there a subset of vertices S, |S|<= k, that dominates all vertices?

A vertex covers it's incident edges and dominates it's neighbors and itself.

Assuming that VC is NPC, prove that DS is NPC.

There is a quite nice and well known reduction:

Given an instance (G,k) of Vertex Cover build an instance of Dominating Set (H,k), where for H you take G, remove all isolated vertices, and for every edge (u,v) add an additional vertex x connected to u and v.

First realize that a Vertex Cover of G is a Dominating Set of H: it's a DS of G (after removing isolated vertices), and the new vertices are also dominated. So if G has a VC smaller k, then H has a DS smaller k.

For the converse, consider D, a Dominating Set of H.

Notice that if one of the new vertices is in D, we can replace it with one of it's two neighbors and still get an Dominating Set: it's only neighbors are are the two original vertices and they are also connected - everything x can possible dominate is also dominated by u or v.

So we can assume that D contains only vertices from G. Now for every edge (u,v) in G the new vertex x is dominated by D, so either u or v is in D. But this means D is a Vertex Cover of G.

And there we have it: G has a Vertex Cover smaller k if and only if H has a Dominating Set smaller k.

Taken from :

CMSC 651 Advanced Algorithms , Lecturer Samir Khuller

I think that second problem is not NP. Let's try the following algorithm.

1. Get the original Graph
2. Run any algorithm which checks if a graph is connected or not.
3. mark all used edges of step 2
4. if the graph is connected then return the set of marked edges otherwise there is no such a set.

If I understood correctly your problem then it is not NP Complete.