# Finding bicliques in a bipartite graph of minimum size

Let $G=(U \cup V, E)$ denotes a bipartite graph. A biclique $C = (U, V)$ is a subgraph of $G$ induced by a pair of two disjoint subsets $U' \subseteq U$, $V' \subseteq V$, such that $\forall u \in U', v \in V': (u, v) \in E$.

Given $\delta$, I'd like to identify bicliques $(U',V')$ such that $|V'| \ge \delta$. Since the number of all bicliques in a bipartite graph w.r.t its size can be exponential, I'm looking for an approximate algorithm (desirably with guarantees), that can find bicliques such that $|V'| \ge \delta$. For example, find $k$ bicliques where $|V'| \geq \delta$, in time polynomial w.r.t. $k$ and $G$. Can anyone suggest such an algorithm?

One naive solution is to enumerate bicliques using an enumeration-based algorithm and keep the bicliques that satisfy the last condition until the selection of "k" bicliques.

Here is an algorithm with $O(n^{2+\lg k})$ running time. It's not polynomial in $k$ and $n$, but for fixed $n$ it is polynomial in $k$, and for fixed $k$ it is polynomial in $n$. Here is the algorithm:

1. Let $\gamma = \lg k$.

2. Find all bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Output $k$ of them (stop early once you have found $k$ of them).

In step 2, it's easy to find all bicliques such that $|U'| \le \gamma$, $|V'| \ge \delta$ in $O(n^{2+\gamma})$ time: just enumerate all possibilities for $U'$. By the definition of $\gamma$, this takes $O(n^{2+\lg k})$ time, since there are only ${|U| \choose 0 } + \dots + {|U| \choose \gamma} = O(|U|^{\gamma}) = O(n^{\gamma}) = O(n^{\lg k})$ possible subsets $U'$ of size $\le \gamma$.

But will step 2 find enough bicliques? You might worry that it will find fewer than $k$ bicliques, even when there are at least $k$ in the graph. Not to worry; that can't happen. In particular, I'll show that if there is a biclique that is too large to be found in step 2, then there are at least $k$ bicliques that are small enough to be found in step 2, so step 2 will find enough to output $k$. The only way that step 2 can fail to output $k$ bicliques is if the graph does not contain $k$ bicliques.

Let's prove that claim. If step 2 outputs fewer than $k$ bicliques and there exists a biclique that the algorithm didn't output, that means there exists a biclique with $|U'| \ge \gamma+1$ and $|V'| \ge \delta$. What are the consequences of this? Well, there are two cases, depending on the size of $U'$:

• Case 1. Suppose $\gamma+1 \le |U'| \le 2\gamma$. Then you can find at least $2^{\gamma}$ more such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Why? Well, take any subset of $U'$ of size at most $\gamma$, and keep $V'$ unchanged. Then this will give a new biclique, and it will meet all the conditions of the original problem. The number of such subsets is ${|U'| \choose 0} + {|U'| \choose 1} + \dots + {|U'| \choose \gamma}$, which is at least $2^{U'}/2$ (since $\gamma \ge |U'|/2$). Now $2^{U'}/2 \ge 2^{\gamma+1}/2 \ge 2^{\gamma} \ge k$, so this gives us $k$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Thus in this case there exist enough bicliques that step 2 can find $k$ of them.

• Case 2. Suppose $|U'| \ge 2\gamma$. Then you can find at least $2^{\gamma}$ more bicliques such that $|U'| \le \gamma$ and $|V'| \ge \delta$. Why? Again, take any subset of $U'$ of size at most $\gamma$; that will lead to another biclique that can be found in step 2. How many such subsets are there? There are at least ${|U'| \choose \gamma}$ of them, and ${|U'| \choose \gamma} \ge (|U'|/\gamma)^{\gamma}$ more (see the first bound here). By assumption, $|U'|/\gamma \ge 2$, so this means there are at least $2^{\gamma}$ more such subsets, i.e., at least $2^{\gamma}$ more bicliques that can be found in step 2. Thus in this case there exist enough bicliques that step 2 can find $k$ of them.

In either case, if the graph has at least $k$ bicliques, this algorithm will output at least $k$ of them.

• Thanks. Could you please clarify more about how can I find all bicliques with that constraint in the mentioned time complexity? a little more details about Step 2. – mhn_namak Mar 16 '18 at 19:33
• Also, I assume the time complexity holds even if I don't stop early as soon as I find "k" bicliques. I'm afraid if I stop early, I just get some small bicliques $|U'|=1$ which is not desirable. – mhn_namak Mar 16 '18 at 19:42
• @mhn_namak, OK, I've edited. The main thing is you need to know how to enumerate all subsets of size $\le \gamma$ from a larger set ; that's not too hard. Sure, my procedure might give you small bicliques with $|U'|=1$. That wasn't mentioned as a consideration or requirement in your question; I can only go based on what is stated in the question. – D.W. Mar 16 '18 at 20:08