I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices.

My question is: are there any positive results in the litterature regarding polynomial time guarenteed approximations for this problem?

On the negative side, we know that no constant factor approximation exists unless $\mathrm{P}=\mathrm{NP}$. Moreover there is some constant $\delta>0$ for which there is no $\delta B$ factor approximation on bipartite graphs with maximum degree bounded by $B$ (for large enough $B$, assuming $\mathrm{P}\neq\mathrm{NP}$). See [M. Chlebík and J. Chlebíková, Approximation Hardness of Dominating Set Problems in Bounded Degree Graphs]. The problem is also more or less inaproximable when not restricted to bipartite graphs.

I was however unable to find anything implying a positive result about polynomial time approximations on bipartite graphs.


1 Answer 1


After a bit more searching, it appears that what I'm looking for is unlikely to exist.

In [1], it is proven that approximating the minimum maximal independence number (which is equivalent to the minimum size of an independent dominating set) within a factor of $O(n^{1-\epsilon})$ is $\mathrm{NP}$-hard for any $\epsilon > 0$. This remains true even when restricted to bipartite graph (this is the part I missed when I first came across this paper).

[1] Halldórsson, Magnús M., Approximating the minimum maximal independence number, Inf. Process. Lett. 46, No. 4, 169-172 (1993). ZBL0778.68041.


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.