<p>What if you simply do the following: Given a graph $G = (V,E)$, construct another graph $G' = (V \cup U, E')$ by subdividing each edge of $G$ in 4 parts; here $U$ is the set of new nodes that we introduced, and $|U| = 3|E|$.</p>

<p>The graph $G'$ is bipartite. Moreover, if $G$ is planar and has max. degree 3, then $G'$ is also planar and has max. degree 3.</p>

<p>Let $D'$ be a (minimum) dominating set for $G'$. Consider an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$. Now clearly at least one of $a,b,c$ is in $D'$. Moreover, if we have more than one of $a,b,c$ in $D'$, we can modify $D'$ so that it remains a valid dominating set and its size does not increase. For example, if we have $a \in D'$ and $c \in D'$, we can equally well remove $c$ from $D'$ and add $y$ to $D'$. Hence w.l.o.g. we have $|D' \cap U| = |E|$.</p>

<p>Then consider $D = D' \cap V$. Assume that $x \in V$ and $x \notin D'$. Then we must have a node $a \in D'$ such that $(x,a) \in E'$. Hence there is an edge $(x,y) \in E$ such that we have a path $(x,a,b,c,y)$ in $G'$. Since $a,b,c \in U$ and $a \in D'$, we have $b, c \notin D'$, and to dominate $c$ we must have $y \in D'$. Hence in $G$ node $y$ is a neighbour of $x$ with $y \in D$. That is, $D$ is a dominating set for $G$.</p>

<p>Conversely, consider a (minimum) dominating set $D$ for $G$. Construct a dominating set $D'$ for $G'$ so that $|D'| = |D| + |E|$ as follows: For an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$, we add $a$ to $D'$ if $x \notin D$ and $y \in D$; we add $c$ to $D'$ if $x \in D$ and $y \notin D$; and otherwise we add $b$ to $D'$. Now it can be checked that $D'$ is a dominating set for $G'$: By construction, all nodes in $U$ are dominated. Now let $x \in V \setminus D'$. Then there is a $y \in V$ such that $(x,y) \in E$, and hence along the path $(x,a,b,c,y)$ we have $a \in D'$, which dominates $x$.</p>

<p>In summary, if $G$ has a dominating set of size $k$, then $G'$ has a dominating set of size at most $k + |E|$, and if $G'$ has a dominating set of size $k + |E|$, then $G$ has a dominating set of size at most $k$.</p>

<p><strong>Edit:</strong> Added an illustration. Top: the original graph $G$; middle: graph $G'$ with a "normalised" dominating set; bottom: graph $G'$ with an arbitrary dominating set.</p>

<p><img src="https://i.sstatic.net/nfLBC.png" alt="An example"></p>

CC BY-SA 3.0
2012-01-21T01:21:55.897Z
Solid answer Jukka!
Gabriel Fair
CC BY-SA 2.5
2010-10-28T17:21:14.190Z
Nice answer.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-11-02T08:33:51.300Z
Thank you, that nicely answers my question (even without the nice pictures;) ) Is anyone aware though of a reference where some other (classical) NP-hard graph problems (eg Vertex Cover or other domination problems) are studied in bipartite planar graphs of bounded degree? I think that should be interesting.
Florent Foucaud
CC BY-SA 2.5
2010-11-02T09:40:42.147Z
If it answers the question, perhaps you should consider *accepting* the answer... :)  Regarding other problems, [vertex cover is easy in any bipartite graph](https://secure.wikimedia.org/wikipedia/en/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29). But I guess edge dominating sets might be a natural problem to study in this setting?
Jukka Suomela
CC BY-SA 2.5
2010-11-02T15:59:07.797Z
Ok thanks for reminding me König's theorem and to check the green checkbox ;)
Florent Foucaud
CC BY-SA 2.5
2010-10-27T16:06:54.453Z
2010-11-01T23:30:47.470Z
2010-11-01T23:30:47.470Z
Jukka Suomela
<p>Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?</p>

<p>I know it is NP-complete for the class of planar graphs of maximum degree 3 (see the Garey and Johnson book), as well as for bipartite graphs of maximum degree 3 (see M. Chlebík and J. Chlebíková, "Approximation hardness of dominating set problems in bounded degree graphs"), but could not find the combination of the two in the literature.</p>

CC BY-SA 2.5
2010-10-27T11:50:38.590Z
Next time please link to the original post if you crosspost.  http://mathoverflow.net/questions/43720/is-the-dominating-set-problem-restricted-to-planar-bipartite-graphs-of-maximum-de.  See also our [FAQ entry about crossposting](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-27T12:27:23.210Z
(1) Is anything known if you increase 3 to some other constant?  (2) Is anything known about the special case where “maximum degree 3” is further restricted to “3-regular”?  (Is it known to be in P?  Is it known to be equivalent to the case of maximum degree 3?)  (3) Out of curiosity, is there any application of this, or are you interested in it solely by itself?  (Just in case, I am not saying that a problem without an application is bad.  I am asking it because if you have some application, it may make the question more interesting.)
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-02T08:23:56.617Z
(1) Not to my knowledge
(2) No. But I expect it to be hard as well
(3) The only application for me would be to get the NP-hardness of some other problems in this same, really restricted, class of graphs
Florent Foucaud
<cc.complexity-theory><graph-theory>
Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?
Florent Foucaud
# Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

(Asked by: username_0 on 2010-10-27)

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?

I know it is NP-complete for the class of planar graphs of maximum degree 3 (see the Garey and Johnson book), as well as for bipartite graphs of maximum degree 3 (see M. Chlebík and J. Chlebíková, "Approximation hardness of dominating set problems in bounded degree graphs"), but could not find the combination of the two in the literature.

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: Next time please link to the original post if you crosspost.  http://mathoverflow.net/questions/43720/is-the-dominating-set-problem-restricted-to-planar-bipartite-graphs-of-maximum-de.  See also our [FAQ entry about crossposting](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231).  
> **username_1**: (1) Is anything known if you increase 3 to some other constant?  (2) Is anything known about the special case where “maximum degree 3” is further restricted to “3-regular”?  (Is it known to be in P?  Is it known to be equivalent to the case of maximum degree 3?)  (3) Out of curiosity, is there any application of this, or are you interested in it solely by itself?  (Just in case, I am not saying that a problem without an application is bad.  I am asking it because if you have some application, it may make the question more interesting.)  
> **username_0**: (1) Not to my knowledge (2) No. But I expect it to be hard as well (3) The only application for me would be to get the NP-hardness of some other problems in this same, really restricted, class of graphs  

---

## 1 answers

### Answer by username_2 on 2010-10-27. Score: 25 | Accepted answer

What if you simply do the following: Given a graph $G = (V,E)$, construct another graph $G' = (V \cup U, E')$ by subdividing each edge of $G$ in 4 parts; here $U$ is the set of new nodes that we introduced, and $|U| = 3|E|$.

The graph $G'$ is bipartite. Moreover, if $G$ is planar and has max. degree 3, then $G'$ is also planar and has max. degree 3.

Let $D'$ be a (minimum) dominating set for $G'$. Consider an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$. Now clearly at least one of $a,b,c$ is in $D'$. Moreover, if we have more than one of $a,b,c$ in $D'$, we can modify $D'$ so that it remains a valid dominating set and its size does not increase. For example, if we have $a \in D'$ and $c \in D'$, we can equally well remove $c$ from $D'$ and add $y$ to $D'$. Hence w.l.o.g. we have $|D' \cap U| = |E|$.

Then consider $D = D' \cap V$. Assume that $x \in V$ and $x \notin D'$. Then we must have a node $a \in D'$ such that $(x,a) \in E'$. Hence there is an edge $(x,y) \in E$ such that we have a path $(x,a,b,c,y)$ in $G'$. Since $a,b,c \in U$ and $a \in D'$, we have $b, c \notin D'$, and to dominate $c$ we must have $y \in D'$. Hence in $G$ node $y$ is a neighbour of $x$ with $y \in D$. That is, $D$ is a dominating set for $G$.

Conversely, consider a (minimum) dominating set $D$ for $G$. Construct a dominating set $D'$ for $G'$ so that $|D'| = |D| + |E|$ as follows: For an edge $(x,y) \in E$ that was subdivided to form a path $(x,a,b,c,y)$ in $G'$, we add $a$ to $D'$ if $x \notin D$ and $y \in D$; we add $c$ to $D'$ if $x \in D$ and $y \notin D$; and otherwise we add $b$ to $D'$. Now it can be checked that $D'$ is a dominating set for $G'$: By construction, all nodes in $U$ are dominated. Now let $x \in V \setminus D'$. Then there is a $y \in V$ such that $(x,y) \in E$, and hence along the path $(x,a,b,c,y)$ we have $a \in D'$, which dominates $x$.

In summary, if $G$ has a dominating set of size $k$, then $G'$ has a dominating set of size at most $k + |E|$, and if $G'$ has a dominating set of size $k + |E|$, then $G$ has a dominating set of size at most $k$.

**Edit:** Added an illustration. Top: the original graph $G$; middle: graph $G'$ with a "normalised" dominating set; bottom: graph $G'$ with an arbitrary dominating set.

![An example](https://i.sstatic.net/nfLBC.png)

> **Comments:**
> **username_4**: Nice answer.  
> **username_0**: Thank you, that nicely answers my question (even without the nice pictures;) ) Is anyone aware though of a reference where some other (classical) NP-hard graph problems (eg Vertex Cover or other domination problems) are studied in bipartite planar graphs of bounded degree? I think that should be interesting.  
> **username_2**: If it answers the question, perhaps you should consider *accepting* the answer... :)  Regarding other problems, [vertex cover is easy in any bipartite graph](https://secure.wikimedia.org/wikipedia/en/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29). But I guess edge dominating sets might be a natural problem to study in this setting?  
> **username_0**: Ok thanks for reminding me König's theorem and to check the green checkbox ;)  
> **username_3**: Solid answer Jukka!  

---

