2
$\begingroup$

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

$\endgroup$
7
  • 2
    $\begingroup$ 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. $\endgroup$ Mar 5, 2014 at 15:38
  • $\begingroup$ @FrançoisG.Dorais How exactly do you add the vertices? I don't quite get it... $\endgroup$ Mar 5, 2014 at 15:39
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2014 at 15:43
  • 1
    $\begingroup$ @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. $\endgroup$
    – usul
    Mar 5, 2014 at 16:00
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 5, 2014 at 16:14

1 Answer 1

9
$\begingroup$

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

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