Proof that Dominating Set is NP-Complete

Question

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 subset 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.

Answer 1

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.

Answer 2

Taken from :

CMSC 651 Advanced Algorithms , Lecturer Samir Khuller