In the balanced biclique in bipartite graphs (MBB) problem we are given a bipartite graph $G = (L,R,E), |L| = |R| = n$ and the goal is to find an induced subgraph of $G$, $G' = (L',R',E')$, with as many vertices as possible, such that it has an equal number of vertices from $L$ and $R$ (i.e., $|L'| = |R'|$) and $G'$ is a biclique: $E' = \{ (\ell,r)~|~\ell \in L',r \in R'\}$. Under various assumptions (e.g., the Small Set Expansion Hypothesis (SSEH)), the problem is known to be hard to approximate within a factor of $n^{1-\varepsilon}$ for any $\varepsilon>0$.

Question: Is the problem still hard to approximate for unbalanced scenarios? e.g., for some arbitrary small $\varepsilon>0$ and bipartite graph $G = (L,R,E)$, is it hard to find a biclique $G' = (L',R',E')$ as a subgraph of $G$ such that $|L'| \geq |L|\cdot(1- \varepsilon)$ and $|R'| \geq |R|\cdot \varepsilon$?

  • 1
    $\begingroup$ Did you mean |𝑅′|≥|𝑅|⋅(1-𝜀) ? $\endgroup$
    – B A
    Oct 26, 2022 at 21:40
  • 1
    $\begingroup$ Can't you show this is hard just by reducing the balanced variant to it? Something like: add $|L|/\epsilon$ fake vertices to $L$ and $R$. For every fake vertex added to $L$, give it edges to all original vertices in $R$. For every fake vertex added to $R$, give it no edges. Or something like that? $\endgroup$
    – Neal Young
    Oct 31, 2022 at 1:55


Your Answer

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