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


1 Answer 1


There is a nice reduction by Chalermsook et al. (WG 2020) 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$.

  • $\begingroup$ This is a very nice reduction! Thank you! $\endgroup$
    – Bell
    Commented Aug 20, 2022 at 4:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.