Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?
$\begingroup$
$\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$– François G. DoraisMar 5, 2014 at 15:38
-
$\begingroup$ @FrançoisG.Dorais How exactly do you add the vertices? I don't quite get it... $\endgroup$– Felix GoldbergMar 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$– François G. DoraisMar 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$– usulMar 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$– François G. DoraisMar 5, 2014 at 16:14
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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$.