5

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

Elham Roshanbin
  • 59
  • 1
  • 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. – Saeed Jun 03 '14 at 14:21
  • Jukaa gave the reduction your are looking for. http://cstheory.stackexchange.com/questions/2505/is-the-dominating-set-problem-restricted-to-planar-bipartite-graphs-of-maximum-d/2508#2508 – Mohammad Al-Turkistany Jun 03 '14 at 14:27
  • @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. – Saeed Jun 03 '14 at 14:29
  • 3
    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 – Marzio De Biasi Jun 03 '14 at 14:59
  • 3
    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. – Marzio De Biasi Jun 03 '14 at 23:43
  • @ Marzio De Biasi, Thank you so much Marzio, I actually need the answer for a reading group, I just started to learn about complexity stuff, and reading the NP-completeness proofs. Ok, I gonna move this to cs.stackexchange.com. But, I found out that the proof is given in the paper: "T. Kikuno, N. Yoshida, and Y. Kakuda. The NP-completeness of the dominating set problem in cubic planar graphs. Transactions of the Institute of Electronics and Communication Engineers of Japan, E63(6):443–444, 1980." Best regards, Elham – user24175 Jun 04 '14 at 09:23

0 Answers0