Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
1  
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 Feb 7 '13 at 18:32
    
Thank you very much, Andrew D. King. I also found that it is NP-complete even for planar 4-regular graphs. –  Martin Manrique Feb 10 '13 at 15:55
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

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

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