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

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

<p>Thanks,
Elham</p>

CC BY-SA 3.0
2014-06-03T14:21:52.730Z
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
CC BY-SA 3.0
2014-06-03T14:27:17.907Z
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
CC BY-SA 3.0
2014-06-03T14:29:49.493Z
@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
CC BY-SA 3.0
2014-06-03T14:59:12.487Z
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
CC BY-SA 3.0
2014-06-03T23:43:59.553Z
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](http://www.nearly42.org/misc/dominating.png). 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
CC BY-SA 3.0
2014-06-04T09:23:40.390Z
@ 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
<np-hardness>
NP-completeness of the Dominating set problem for planar graphs of maximum degree 3?
Elham Roshanbin
# NP-completeness of the Dominating set problem for planar graphs of maximum degree 3?

(Asked by: username_0 on 2014-06-03)

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

**Tags:** np-hardness
> **Comments:**
> **username_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.  
> **username_2**: 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  
> **username_1**: @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.  
> **username_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  
> **username_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](http://www.nearly42.org/misc/dominating.png). 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.  
> **username_4**: @ 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  

---

## 0 answers

