<p>After a bit more searching, it appears that what I'm looking for is unlikely to exist.</p>
<p>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 <span class="math-container">$O(n^{1-\epsilon})$</span> is <span class="math-container">$\mathrm{NP}$</span>-hard for any <span class="math-container">$\epsilon &gt; 0$</span>. This remains true even when restricted to bipartite graph (this is the part I missed when I first came across this paper).</p>
<p>[1] <em>Halldórsson, Magnús M.</em>, <a href="http://dx.doi.org/10.1016/0020-0190(93)90022-2" rel="nofollow noreferrer"><strong>Approximating the minimum maximal independence number</strong></a>, Inf. Process. Lett. 46, No. 4, 169-172 (1993). <a href="https://zbmath.org/?q=an:0778.68041" rel="nofollow noreferrer">ZBL0778.68041</a>.</p>

CC BY-SA 4.0
2021-03-26T22:50:23.170Z
2021-03-26T22:50:23.170Z
Tassle
<p>I'm interested in the following problem: given a bipartite graph, find the smallest independent set of vertices which dominate all other vertices.</p>
<p>My question is: <em>are there any positive results in the litterature regarding polynomial time guarenteed approximations for this problem?</em></p>
<p>On the negative side, we know that no constant factor approximation exists unless <span class="math-container">$\mathrm{P}=\mathrm{NP}$</span>. Moreover there is some constant <span class="math-container">$\delta&gt;0$</span> for which there is no <span class="math-container">$\delta B$</span> factor approximation on bipartite graphs with maximum degree bounded by <span class="math-container">$B$</span> (for large enough <span class="math-container">$B$</span>, assuming <span class="math-container">$\mathrm{P}\neq\mathrm{NP}$</span>). 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.</p>
<p>I was however unable to find anything implying a positive result about polynomial time approximations on bipartite graphs.</p>

<reference-request><graph-algorithms><approximation-algorithms><approximation-hardness>
Approximating Independent Dominating set on bipartite graphs
Tassle
# Approximating Independent Dominating set on bipartite graphs

(Asked by: username_0 on 2021-03-25)

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.

**Tags:** reference-request, graph-algorithms, approximation-algorithms, approximation-hardness

---

## 1 answers

### Answer by username_0 on 2021-03-26. Score: 1 | Accepted answer

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**](http://dx.doi.org/10.1016/0020-0190(93)90022-2), Inf. Process. Lett. 46, No. 4, 169-172 (1993). [ZBL0778.68041](https://zbmath.org/?q=an:0778.68041).


---

