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?
$\begingroup$
$\endgroup$
2
asked Mar 31, 2012 at 7:59
-
$\begingroup$ Some time ago, I wrote this up on there being multiple approaches for finding $2$ x $k$ bicliques: cstheory.stackexchange.com/a/44177/14207 $\endgroup$– Michael WeharAug 10, 2020 at 19:27
-
$\begingroup$ I'm very interested in this problem and would always be open to discussing. :) $\endgroup$– Michael WeharAug 10, 2020 at 19:28
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
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.
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.
answered Mar 31, 2012 at 18:31
-
$\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$ Mar 31, 2012 at 18:37
$\begingroup$
$\endgroup$
0
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. Inf. Process. Lett. 111(2): 64-67 (2010)
Jean-François Couturier, Dieter Kratsch:Bicolored independent sets
and bicliques. Inf. Process. Lett. 112(8-9): 329-334 (2012)
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
1
(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)}$.
-
8$\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$ Apr 1, 2012 at 3:28