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.