I am trying to learn about some techniques that are used for proving the NP-completeness of domination related problems. One of the problems that is known to be NP-complete is the domination number of planar graphs with maximum degree 3 (Garey and Johnson). Everybody in any paper and book, they refer to Garey and Johnson book, but there is no proof there, cause Garey and Johnson book refer to a reference at the end of the book which is unpublished.

Does any body know what is a proof for this problem, or any reference for it?

Thanks, Elham

  • $\begingroup$ I don't know the proof but some points: 1. Gary and Johnson are usually mentioning by use of which problem (if the reference is personal communication, ...). 2. Is it hard to use planar vertex cover or planar 3-SAT, these are first things in top of my head. 3. What is the usage of this, suppose you got the proof then what happens in the TCS or for you? 4. Because you didn't mention what have you tried (which problem you tried to reduce from but you failed) I think your question is not a research level and more or less looks like a homework. $\endgroup$ – Saeed Jun 3 '14 at 14:21
  • $\begingroup$ Jukaa gave the reduction your are looking for. cstheory.stackexchange.com/questions/2505/… $\endgroup$ – Mohammad Al-Turkistany Jun 3 '14 at 14:27
  • $\begingroup$ @MohammadAl-Turkistany, That's a different problem and Jukaa by use of this fact (theorem) proved the other one (not from scratch), it does not work other way around. $\endgroup$ – Saeed Jun 3 '14 at 14:29
  • 3
    $\begingroup$ There is a quick reduction from the Hamiltonian cycle problem on planar graphs with max deg. 3, but you can also start directly from planar 3-SAT $\endgroup$ – Marzio De Biasi Jun 3 '14 at 14:59
  • 3
    $\begingroup$ For a direct reduction from planar 3SAT the ingredients you should boil together are: positive/negative variable gadgets, wires, wire splitters, OR gadgets, clause vertices. Every single piece/gadget must require a minimum fixed number of dominating vertices. This figure shows a possible way of implementing a wire and an OR gadget. It is not a research level question, so flag it and ask to move it on cs.stackexchange.com and I'll convert this comment into an answer with more details. $\endgroup$ – Marzio De Biasi Jun 3 '14 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.