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

5
задан ian 25 May 2012 в 10:22
поделиться