Talk:Dominating set problem

The language of this page needs to be cleaned up, especially the section containing the reduction from vertex cover. I removed some minor spelling and grammatical errors, but amost the whole section needs to be rewritten. The content seems OK. DVanDyck 13:31, 13 September 2006 (UTC)Reply

I'd appreciate if someone could explain why this is not a counter-example: a graph with two vertices, A and B, and no edge between them. There's a vertex cover of size 0, namely the empty set. The reduction described is idempotent on this graph (there are no edges, so no new vertices or edges are added). However, there is no dominating set of size 0; the smallest dominating set is {A,B}, i.e., of size 2. 76.182.204.23 05:16, 26 March 2007 (UTC)Reply

The problem asks for a positive integer k. 0 is nonnegative but not positive. 71.121.137.70 06:16, 25 May 2007 (UTC)ZrflxReply

I think the proof is not quite correct.

(${\displaystyle \Rightarrow }$) D is a dominating set of size k in G '. So, every edge hits some vertex in D. D is a vertex cover in G of size k.

This is not true, because not all vertices in D are vertices in G. You have to "move" them to adjacent G-vertices first. --129.59.223.115 20:10, 20 June 2007 (UTC)Reply

I noticed that we have Yannakakis and Gavril (1978) in the list of references. The paper is about edge dominating sets. This page is about dominating sets, and we do not mention edge dominating sets.

Should we (a) remove the reference or (b) add something about edge dominating sets here?

(In the case b, we should also update the reference. The paper has appeared in SIAM Journal on Applied Mathematics 38:3(1980), p. 364-372 [1].) —Preceding unsigned comment added by Miym (talk • contribs) 13:55, 10 December 2008 (UTC)Reply