Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
Next time please link to the original post if you crosspost. mathoverflow.net/questions/43720/…. 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 2 '10 at 8:23
    
BTW, thanks for crossposting. –  Florent Foucaud Nov 2 '10 at 8:26
add comment

1 Answer

up vote 21 down vote accepted

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

share|improve this answer
    
Nice answer. –  Mohammad Al-Turkistany Oct 28 '10 at 17:21
    
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 Nov 2 '10 at 8:33
1  
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? –  Jukka Suomela Nov 2 '10 at 9:40
    
Ok thanks for reminding me König's theorem and to check the green checkbox ;) –  Florent Foucaud Nov 2 '10 at 15:59
    
Solid answer Jukka! –  Gabriel Fair Jan 21 '12 at 1:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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