<p>There is a nice reduction by <a href="https://link.springer.com/chapter/10.1007/978-3-030-60440-0_19" rel="nofollow noreferrer">Chalermsook et al. (WG 2020)</a> that can give the kind of approximation you want. I'll describe it below in terms of finding balanced <em>complete bipartite subgraph (biclique)</em> instead of independent set for simplicity (and consistency with the Chalermsook et al.'s paper). The two problems are equivalent.</p>
<p>The idea is to partition the <em>edges</em> of the input graph <span class="math-container">$G$</span> into <span class="math-container">$n$</span> disjoint matchings <span class="math-container">$E_1, \dots, E_n$</span>. Then, we may create a graph <span class="math-container">$G_i$</span> for each <span class="math-container">$E_i$</span> by viewing each <em>edge</em> as a <em>vertex</em>, and we link two vertices <span class="math-container">$e = (u, v), e' = (u', v')$</span> in <span class="math-container">$G_i$</span> iff the edges <span class="math-container">$(u, v')$</span> and <span class="math-container">$(u', v)$</span> are present in the original graph <span class="math-container">$G$</span>.</p>
<p>There are two simple observations regarding this reduction:</p>
<ol>
<li><p>Any <span class="math-container">$k$</span>-clique in <span class="math-container">$G_i$</span> corresponds to a <span class="math-container">$k$</span>-balanced biclique.</p>
</li>
<li><p>Any <span class="math-container">$k$</span>-balanced biclique has <span class="math-container">$k^2$</span> edges, so at least one of the partition <span class="math-container">$E_i$</span> must contains at least <span class="math-container">$(k^2/n)$</span> edges from the biclique. This means that <span class="math-container">$G_i$</span> contains a <span class="math-container">$(k^2/n)$</span>-clique.</p>
</li>
</ol>
<p>Now, if you have a <span class="math-container">$\alpha n$</span>-balanced biclique in the original graph for some <span class="math-container">$\alpha \in (0, 1)$</span>, 2. tells you that at least on of the <span class="math-container">$G_i$</span> contains <span class="math-container">$\alpha^2 n$</span>-clique. You can then apply the algorithm from Alon-Kahale to get <span class="math-container">$n^{f(\alpha^2)}$</span>-clique in <span class="math-container">$G_i$</span> (where <span class="math-container">$f$</span> denote the exponent guarantee by the clique algorithm, e.g. <span class="math-container">$f(\alpha^2) = \Omega(1/\alpha^2)$</span> in Alon-Kahale). Using 1. this then gives you <span class="math-container">$n^{f(\alpha^2)}$</span>-balanced biclique in the original graph <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2022-08-20T04:34:40.353Z
This is a very nice reduction! Thank you!
Bell
CC BY-SA 4.0
2022-08-19T15:00:31.713Z
2022-08-19T15:07:01.327Z
2022-08-19T15:07:01.327Z
Pasin Manurangsi
<p><strong>The Problem:</strong> Given a bipartite graph <span class="math-container">$G = (L,R,E)$</span> with <span class="math-container">$|L|=|R|=n$</span>, the <strong>balanced bipartite independent set</strong> problem asks us to output the largest vertex subsets <span class="math-container">$A\subseteq L, B\subseteq R$</span> of equal size (i.e. <span class="math-container">$|A| = |B|$</span>) such that there is no edge between <span class="math-container">$A,B$</span>. This problem is known to be NP-hard. In fact, assuming Small Set Expansion Hypothesis, no polynomial-time algorithm can approximate this problem to within a factor of <span class="math-container">$n^{1-\epsilon}$</span> for every constant <span class="math-container">$\epsilon &gt; 0$</span> (see the result by Manurangsi: <a href="https://arxiv.org/abs/1705.03581" rel="nofollow noreferrer">https://arxiv.org/abs/1705.03581</a>).</p>
<p><strong>Question:</strong> Is it possible to obtain better poly-time approximation for this problem if one is promised that the answer is <span class="math-container">$\Omega(n)$</span>? For example, can one find a balanced independent set of size <span class="math-container">$\Omega(n^{\delta})$</span> for some constant <span class="math-container">$\delta &gt; 0$</span>?</p>
<p><strong>Context:</strong> The reason I ask the question is because this kind of approximation is achievable for general independent set by a result of Alon and Kahale: <a href="https://www.cs.tau.ac.il/%7Enogaa/PDFS/indep7.pdf" rel="nofollow noreferrer">https://www.cs.tau.ac.il/~nogaa/PDFS/indep7.pdf</a>. Specifically, although the maximum independent size of a graph is NP-hard to approximate to within a factor of <span class="math-container">$O(n^{1-\epsilon})$</span> for any constant <span class="math-container">$\epsilon &gt; 0$</span>, they showed that whenever there exists an independent set of size <span class="math-container">$\Omega(n)$</span>, one can find one of size <span class="math-container">$\Omega(n^{\delta})$</span> for some constant <span class="math-container">$\delta &gt; 0$</span> in polynomial time. Therefore I was wondering if one can achieve the same for balanced bipartite independent set as well.</p>

<approximation-algorithms><approximation-hardness><clique><semidefinite-programming><independent-set>
Approximation algorithm for balanced bipartite independent set?
Bell
# Approximation algorithm for balanced bipartite independent set?

(Asked by: username_0 on 2022-08-19)

**The Problem:** Given a bipartite graph $G = (L,R,E)$ with $|L|=|R|=n$, the **balanced bipartite independent set** problem asks us to output the largest vertex subsets $A\subseteq L, B\subseteq R$ of equal size (i.e. $|A| = |B|$) such that there is no edge between $A,B$. This problem is known to be NP-hard. In fact, assuming Small Set Expansion Hypothesis, no polynomial-time algorithm can approximate this problem to within a factor of $n^{1-\epsilon}$ for every constant $\epsilon > 0$ (see the result by Manurangsi: <https://arxiv.org/abs/1705.03581>).

**Question:** Is it possible to obtain better poly-time approximation for this problem if one is promised that the answer is $\Omega(n)$? For example, can one find a balanced independent set of size $\Omega(n^{\delta})$ for some constant $\delta > 0$?

**Context:** The reason I ask the question is because this kind of approximation is achievable for general independent set by a result of Alon and Kahale: [https://www.cs.tau.ac.il/~nogaa/PDFS/indep7.pdf](https://www.cs.tau.ac.il/%7Enogaa/PDFS/indep7.pdf). Specifically, although the maximum independent size of a graph is NP-hard to approximate to within a factor of $O(n^{1-\epsilon})$ for any constant $\epsilon > 0$, they showed that whenever there exists an independent set of size $\Omega(n)$, one can find one of size $\Omega(n^{\delta})$ for some constant $\delta > 0$ in polynomial time. Therefore I was wondering if one can achieve the same for balanced bipartite independent set as well.

**Tags:** approximation-algorithms, approximation-hardness, clique, semidefinite-programming, independent-set


---

## 1 answers

### Answer by username_1 on 2022-08-19. Score: 3 | Accepted answer

There is a nice reduction by [Chalermsook et al. (WG 2020)](https://link.springer.com/chapter/10.1007/978-3-030-60440-0_19) that can give the kind of approximation you want. I'll describe it below in terms of finding balanced *complete bipartite subgraph (biclique)* instead of independent set for simplicity (and consistency with the Chalermsook et al.'s paper). The two problems are equivalent.

The idea is to partition the *edges* of the input graph $G$ into $n$ disjoint matchings $E\_1, \dots, E\_n$. Then, we may create a graph $G\_i$ for each $E\_i$ by viewing each *edge* as a *vertex*, and we link two vertices $e = (u, v), e' = (u', v')$ in $G\_i$ iff the edges $(u, v')$ and $(u', v)$ are present in the original graph $G$.

There are two simple observations regarding this reduction:

1. Any $k$-clique in $G\_i$ corresponds to a $k$-balanced biclique.
2. Any $k$-balanced biclique has $k^2$ edges, so at least one of the partition $E\_i$ must contains at least $(k^2/n)$ edges from the biclique. This means that $G\_i$ contains a $(k^2/n)$-clique.

Now, if you have a $\alpha n$-balanced biclique in the original graph for some $\alpha \in (0, 1)$, 2. tells you that at least on of the $G\_i$ contains $\alpha^2 n$-clique. You can then apply the algorithm from Alon-Kahale to get $n^{f(\alpha^2)}$-clique in $G\_i$ (where $f$ denote the exponent guarantee by the clique algorithm, e.g. $f(\alpha^2) = \Omega(1/\alpha^2)$ in Alon-Kahale). Using 1. this then gives you $n^{f(\alpha^2)}$-balanced biclique in the original graph $G$.

> **Comments:**
> **username_0**: This is a very nice reduction! Thank you!  

---

