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

In , 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).