<p>The following papers provide exponential-time algorithms for the non-induced biclique problem and may be of interest to you :</p>

<ul>
<li><p>Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu
Liedloff: <a href="http://www.sciencedirect.com/science/article/pii/S0020019010003261" rel="noreferrer">Exact exponential-time algorithms for finding bicliques</a>.
Inf. Process. Lett. 111(2): 64-67 (2010)</p></li>
<li><p>Jean-François Couturier, Dieter Kratsch:<a href="http://www.sciencedirect.com/science/article/pii/S0020019012000270" rel="noreferrer">Bicolored independent sets<br>
and bicliques</a>. Inf. Process. Lett. 112(8-9): 329-334 (2012)</p></li>
</ul>

CC BY-SA 3.0
2012-04-02T09:11:16.280Z
2012-04-02T12:53:52.087Z
2012-04-02T12:53:52.087Z
Limath
<p>This approximation
"Nuclear norm minimization for the planted clique and biclique problems", by B. Ames
and S. Vavasis ( <a href="http://arxiv.org/pdf/0901.3348.pdf" rel="noreferrer">http://arxiv.org/pdf/0901.3348.pdf</a> ) finds a biclique for some specific type of graphs in poly-time, but has no general approximation guarantees.</p>

<p>The authors recast the biclique problem to a rank minimization, subject to affine constraints. Then, they solve a relaxation using a nuclear norm heuristic, which can be posed as an SDP. This heuristic is a pretty exciting gadget of the compressed sensing paraphernalia. This relaxation usually admits some cute optimality conditions when the set of constraints exhibit "an appropriate type" of randomness.</p>

CC BY-SA 3.0
2012-03-31T19:18:06.630Z
2012-03-31T19:23:10.663Z
2012-03-31T19:23:10.663Z
Dimitris
<p><strong>(WRONG ANSWER: this answer is wrong -- see David Eppstein's comment below. I'm leaving it here for posterity.)</strong></p>
<p>It is worth noting that finding a k by k biclique in an n-vertex graph is as least as hard as finding a size-k clique in an (n/2)-vertex graph: simply take the (n/2) vertex graph, and convert it to a bipartite graph in the obvious way (each vertex v turns into two vertices v1,v2 which are connected by an edge, and each edge (u,v) turns into two edges: (u1,v2) and (u2,v1) ). Since finding a size-k clique is W[1]-hard, then finding a biclique is also W[1]-hard, and so is conjectured to not have an algorithm with running time <span class="math-container">$n^{o(k)}$</span>.</p>

CC BY-SA 3.0
2012-04-01T03:28:40.960Z
I don't think this reduction works. If your initial graph already had a big biclique in it, then the graph you form from it (its bipartite double cover) would still have the same biclique, masking whether or not the original graph also had a clique.
David Eppstein
CC BY-SA 4.0
2012-04-01T00:51:35.737Z
2020-08-01T16:01:10.377Z
2020-08-01T16:01:10.377Z
Elad
<p>Parameterized by degeneracy or arboricity, it's FPT. More specifically, $O(d^3 2^d n)$ where $d$ is the degeneracy (or $a^3 2^{2a}$ for arboricity). See: </p>

<ul>
<li>Arboricity and bipartite subgraph listing algorithms.
D. Eppstein.
<a href="http://dx.doi.org/10.1016/0020-0190%2894%2990121-X" rel="nofollow">Inf. Proc. Lett. 51:207-211, 1994</a>.</li>
</ul>

<p>Another parameterized paper has just been <a href="http://swat2012.helsinki.fi/programme/#papers" rel="nofollow">accepted to SWAT 2012</a>, this time parameterized by longest induced path length:</p>

<ul>
<li>Aistis Atminas, Vadim Lozin and Igor Razgon: 
Linear time algorithm for computing a small biclique in graphs without long induced paths. SWAT 2012, to appear.</li>
</ul>

<p>But my understanding is that whether this is FPT or not with the natural parameter (the size of the biclique) is a big open problem.</p>

CC BY-SA 3.0
2012-03-31T18:37:33.650Z
Thank you David. Note that I'm not just wondering if it's FPT w.r.t. k but rather if there is *anything* better than the naïve algorithm I sketched. In particular, is finding apparently easier than counting.
Andreas Björklund
CC BY-SA 3.0
2012-03-31T18:31:39.340Z
2012-04-07T15:27:00.730Z
2012-04-07T15:27:00.730Z
David Eppstein
<p>Given an $n$ vertex undirected graph, what is the best known runtime bound for <em>finding</em> a subgraph which is a $k\times k$-biclique? Are there faster parametrized algorithms than the
$\binom{n}{k}\mbox{poly}(n)$ time algorithm of "guessing" one side of the biclique and see if there are at least $k$ other vertices incident to all of them?</p>

CC BY-SA 4.0
2020-08-10T19:27:05.663Z
Some time ago, I wrote this up on there being multiple approaches for finding $2$ x $k$ bicliques: https://cstheory.stackexchange.com/a/44177/14207
Michael Wehar
CC BY-SA 4.0
2020-08-10T19:28:15.660Z
I'm very interested in this problem and would always be open to discussing.  :)
Michael Wehar
<ds.algorithms><reference-request><graph-algorithms><parameterized-complexity>
Parametrized Algorithm for Finding Bicliques
Andreas Björklund
# Parametrized Algorithm for Finding Bicliques

(Asked by: username_0 on 2012-03-31)

Given an $n$ vertex undirected graph, what is the best known runtime bound for *finding* a subgraph which is a $k\times k$-biclique? Are there faster parametrized algorithms than the
$\binom{n}{k}\mbox{poly}(n)$ time algorithm of "guessing" one side of the biclique and see if there are at least $k$ other vertices incident to all of them?

**Tags:** ds.algorithms, reference-request, graph-algorithms, parameterized-complexity
> **Comments:**
> **username_1**: Some time ago, I wrote this up on there being multiple approaches for finding $2$ x $k$ bicliques: https://cstheory.stackexchange.com/a/44177/14207  
> **username_1**: I'm very interested in this problem and would always be open to discussing.  :)  

---

## 4 answers

### Answer by username_5 on 2012-03-31. Score: 11 | Accepted answer

Parameterized by degeneracy or arboricity, it's FPT. More specifically, $O(d^3 2^d n)$ where $d$ is the degeneracy (or $a^3 2^{2a}$ for arboricity). See:

* Arboricity and bipartite subgraph listing algorithms.
  D. Eppstein.
  [Inf. Proc. Lett. 51:207-211, 1994](http://dx.doi.org/10.1016/0020-0190%2894%2990121-X).

Another parameterized paper has just been [accepted to SWAT 2012](http://swat2012.helsinki.fi/programme/#papers), this time parameterized by longest induced path length:

* Aistis Atminas, Vadim Lozin and Igor Razgon:
  Linear time algorithm for computing a small biclique in graphs without long induced paths. SWAT 2012, to appear.

But my understanding is that whether this is FPT or not with the natural parameter (the size of the biclique) is a big open problem.

> **Comments:**
> **username_0**: Thank you David. Note that I'm not just wondering if it's FPT w.r.t. k but rather if there is *anything* better than the naïve algorithm I sketched. In particular, is finding apparently easier than counting.  

---

### Answer by username_2 on 2012-04-02. Score: 8

The following papers provide exponential-time algorithms for the non-induced biclique problem and may be of interest to you :

* Daniel Binkele-Raible, Henning Fernau, Serge Gaspers, Mathieu
  Liedloff: [Exact exponential-time algorithms for finding bicliques](http://www.sciencedirect.com/science/article/pii/S0020019010003261).
  Inf. Process. Lett. 111(2): 64-67 (2010)
* Jean-François Couturier, Dieter Kratsch:[Bicolored independent sets  
  and bicliques](http://www.sciencedirect.com/science/article/pii/S0020019012000270). Inf. Process. Lett. 112(8-9): 329-334 (2012)


---

### Answer by username_3 on 2012-03-31. Score: 5

This approximation
"Nuclear norm minimization for the planted clique and biclique problems", by B. Ames
and S. Vavasis ( <http://arxiv.org/pdf/0901.3348.pdf> ) finds a biclique for some specific type of graphs in poly-time, but has no general approximation guarantees.

The authors recast the biclique problem to a rank minimization, subject to affine constraints. Then, they solve a relaxation using a nuclear norm heuristic, which can be posed as an SDP. This heuristic is a pretty exciting gadget of the compressed sensing paraphernalia. This relaxation usually admits some cute optimality conditions when the set of constraints exhibit "an appropriate type" of randomness.


---

### Answer by username_4 on 2012-04-01. Score: 0

**(WRONG ANSWER: this answer is wrong -- see David Eppstein's comment below. I'm leaving it here for posterity.)**

It is worth noting that finding a k by k biclique in an n-vertex graph is as least as hard as finding a size-k clique in an (n/2)-vertex graph: simply take the (n/2) vertex graph, and convert it to a bipartite graph in the obvious way (each vertex v turns into two vertices v1,v2 which are connected by an edge, and each edge (u,v) turns into two edges: (u1,v2) and (u2,v1) ). Since finding a size-k clique is W[1]-hard, then finding a biclique is also W[1]-hard, and so is conjectured to not have an algorithm with running time $n^{o(k)}$.

> **Comments:**
> **username_5**: I don't think this reduction works. If your initial graph already had a big biclique in it, then the graph you form from it (its bipartite double cover) would still have the same biclique, masking whether or not the original graph also had a clique.  

---

