Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. 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
1  
The minimum edge dominating set is NP-hard in bipartite graphs of maximum degree 3, but I think this doesn't help with your problem. Posting at cstheory.stackexchange.com might widen the pool of experts... –  Joseph O'Rourke Oct 27 '10 at 1:04
    
Ok thanks - I just heard about this website, I didn't know there are other similar ones ;) –  Florent Foucaud Oct 27 '10 at 11:29
    
And here is the link: cstheory.stackexchange.com/questions/2505/… –  Jukka Suomela Oct 27 '10 at 17:31
1  
The problem remains NP-complete even for planar bipartite graphs of maximum degree 3. See the nice reduction by @Jukka Suomela at cstheory.stackexchange.com/questions/2505/… which works by introducing 3 new vertices in each edge. –  András Salamon Mar 18 '11 at 18:31
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.