1
$\begingroup$

Hi,

I believe it is just an easy question, but I have not found the answer: Is the optimization / decision problem DOMINATING SET NP-complete when restricted to regular graphs? Where can I find a proof of that?

Thank you, MO users.

$\endgroup$
2
  • 1
    $\begingroup$ Dominating set is NP-complete, and even APX-complete, for cubic graphs. dx.doi.org/10.1016/S0304-3975(98)00158-3 $\endgroup$ Feb 7, 2013 at 18:32
  • $\begingroup$ Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. $\endgroup$ Feb 10, 2013 at 15:55

1 Answer 1

3
$\begingroup$

Dominating set is NP-complete, and even APX-complete, for cubic graphs. dx.doi.org/10.1016/S0304-3975(98)00158-3 – Andrew D. King

Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. – Martin Manrique

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.