MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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.