Parametrized Algorithm for Finding Bicliques 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?
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.