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.

  • 1
    $\begingroup$ 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... $\endgroup$ Oct 27, 2010 at 1:04
  • $\begingroup$ Ok thanks - I just heard about this website, I didn't know there are other similar ones ;) $\endgroup$ Oct 27, 2010 at 11:29
  • 1
    $\begingroup$ And here is the link: cstheory.stackexchange.com/questions/2505/… $\endgroup$ Oct 27, 2010 at 17:31
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 18, 2011 at 18:31


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.