8
$\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.

Improve this question
$\endgroup$
4
  • 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$
    – Joseph O'Rourke
    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$
    – Florent Foucaud
    Oct 27, 2010 at 11:29
  • 1
    $\begingroup$ And here is the link: cstheory.stackexchange.com/questions/2505/… $\endgroup$
    – Jukka Suomela
    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$
    – András Salamon
    Mar 18, 2011 at 18:31

0

Reset to default

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.