16
$\begingroup$

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?

$\endgroup$
8
$\begingroup$

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:

Another parameterized paper has just been accepted to SWAT 2012, 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andreas Björklund Mar 31 '12 at 18:37
5
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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)}$.

$\endgroup$
  • 6
    $\begingroup$ 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. $\endgroup$ – David Eppstein Apr 1 '12 at 3:28

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.