19

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.

Florent Foucaud
  • 2,153
  • 12
  • 27
  • 3
    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. – Tsuyoshi Ito Oct 27 '10 at 11:50
  • 3
    (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 Oct 27 '10 at 12:27
  • (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 Nov 02 '10 at 08:23

1 Answers1

25

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

Jukka Suomela
  • 11,500
  • 2
  • 53
  • 116