19
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Next time please link to the original post if you crosspost. mathoverflow.net/questions/43720/…. See also our FAQ entry about crossposting. $\endgroup$ Oct 27, 2010 at 11:50
  • 3
    $\begingroup$ (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.) $\endgroup$ Oct 27, 2010 at 12:27
  • $\begingroup$ (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 $\endgroup$ Nov 2, 2010 at 8:23

1 Answer 1

25
$\begingroup$

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

$\endgroup$
5
  • 1
    $\begingroup$ Nice answer. $\endgroup$ Oct 28, 2010 at 17:21
  • $\begingroup$ 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. $\endgroup$ Nov 2, 2010 at 8:33
  • 2
    $\begingroup$ If it answers the question, perhaps you should consider accepting the answer... :) Regarding other problems, vertex cover is easy in any bipartite graph. But I guess edge dominating sets might be a natural problem to study in this setting? $\endgroup$ Nov 2, 2010 at 9:40
  • $\begingroup$ Ok thanks for reminding me König's theorem and to check the green checkbox ;) $\endgroup$ Nov 2, 2010 at 15:59
  • $\begingroup$ Solid answer Jukka! $\endgroup$ Jan 21, 2012 at 1:21

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.