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
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 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:… – Jukka Suomela Oct 27 '10 at 17:31
The problem remains NP-complete even for planar bipartite graphs of maximum degree 3. See the nice reduction by @Jukka Suomela at… which works by introducing 3 new vertices in each edge. – András Salamon Mar 18 '11 at 18:31

Your Answer


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

Browse other questions tagged or ask your own question.