<p>In the balanced biclique in bipartite graphs (MBB) problem we are given a bipartite graph <span class="math-container">$G = (L,R,E), |L| = |R| = n$</span> and the goal is to find an induced subgraph of <span class="math-container">$G$</span>, <span class="math-container">$G' = (L',R',E')$</span>, with as many vertices as possible, such that it has an equal number of vertices from <span class="math-container">$L$</span> and <span class="math-container">$R$</span> (i.e., <span class="math-container">$|L'| = |R'|$</span>) and <span class="math-container">$G'$</span> is a biclique: <span class="math-container">$E' = \{ (\ell,r)~|~\ell \in L',r \in R'\}$</span>. Under various assumptions (e.g., the Small Set Expansion Hypothesis (SSEH)), the problem is known to be hard to approximate within a factor of <span class="math-container">$n^{1-\varepsilon}$</span> for any <span class="math-container">$\varepsilon&gt;0$</span>.</p>
<p><strong>Question:</strong> Is the problem still hard to approximate for unbalanced scenarios? e.g., for some arbitrary small <span class="math-container">$\varepsilon&gt;0$</span> and bipartite graph <span class="math-container">$G = (L,R,E)$</span>, is it hard to find a biclique <span class="math-container">$G' = (L',R',E')$</span> as a subgraph of <span class="math-container">$G$</span> such that <span class="math-container">$|L'| \geq |L|\cdot(1- \varepsilon)$</span> and <span class="math-container">$|R'| \geq |R|\cdot \varepsilon$</span>?</p>

CC BY-SA 4.0
2022-10-26T21:40:18.940Z
Did you mean |′|≥||⋅(1-) ?
B A
CC BY-SA 4.0
2022-10-31T01:55:56.743Z
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?
Neal Young
<approximation-hardness><clique><bipartite-graphs>
Is Finding an *Unbalanced* Biclique in Bipartite Graphs Hard?
John
# Is Finding an *Unbalanced* Biclique in Bipartite Graphs Hard?

(Asked by: username_0 on 2022-10-24)

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$?

**Tags:** approximation-hardness, clique, bipartite-graphs
> **Comments:**
> **username_1**: Did you mean |′|≥||⋅(1-) ?  
> **username_2**: 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?  

---

## 0 answers

