Approximating Independent Dominating set on bipartite graphs 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&gt;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.
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 &gt; 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.