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

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?

share|improve this question
2  
You can always add a three new vertices in a triangle to a bipartite graph to obtain a non-bipartite graph whose domination number is not easier to compute than that of the original bipartite graph. –  François G. Dorais Mar 5 at 15:38
    
@FrançoisG.Dorais How exactly do you add the vertices? I don't quite get it... –  Felix Goldberg Mar 5 at 15:39
    
Create new graph consisting of an copy of the original bipartite graph and a disjoint copy of $K_3$. The domination number of the new (non-bipartite) graph is exactly one more than that of the original bipartite graph. So computing the domination number of the new graph is exactly as hard as computing that of the original bipartite graph. –  François G. Dorais Mar 5 at 15:43
1  
@FrançoisG.Dorais, to show hardness, I think we must reduce the other way: Given an arbitrary graph, show how to convert it to a bipartite graph whose domination number tells you the domination number of the original. –  usul Mar 5 at 16:00
1  
@usul: You're misreading, the question is about the restriction to non-bipartite graphs. My reduction shows that the non-bipartite case is just as hard as the general case. To see that the restriction to bipartite graphs is also NP hard, there is an easy reduction of set covering to domination for bipartite graphs. –  François G. Dorais Mar 5 at 16:14

1 Answer 1

up vote 9 down vote accepted

The general case of the domination number problem reduces to the non-bipartite case. Given a (possibly bipartite graph) $G$, create new graph $G'$ consisting of an copy of $G$ and a disjoint copy of $K_3$. The domination number of the new (non-bipartite) graph $G'$ is exactly one more than that of the original graph $G$. So computing the domination number of the new graph $G'$ is exactly as hard as computing that of the original graph $G$.

share|improve this answer

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.