2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – mhn_namak Mar 16 '18 at 19:33
  • $\begingroup$ 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. $\endgroup$ – mhn_namak Mar 16 '18 at 19:42
  • 1
    $\begingroup$ @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. $\endgroup$ – D.W. Mar 16 '18 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.