5
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\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, 2014 at 14:21
  • $\begingroup$ Jukaa gave the reduction your are looking for. cstheory.stackexchange.com/questions/2505/… $\endgroup$
    – Mohammad Al-Turkistany
    Jun 3, 2014 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, 2014 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, 2014 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, 2014 at 23:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.