Clique problem is a well known $NP$-complete problem where the size of the required clique is part of the input. However, k-clique problem has a trivial polynomial time algorithm ($O(n^k)$ when $k$ is constant). I'm interested in the best known upper bounds when k is constant.
Is there an algorithm with run time $O(n^{k-1})$? A $o(n^k)$-time algorithm is also acceptable. Also, Is there any complexity-theoretic consequence for the existence of such algorithms?
A 3-clique can be found in an $n$-vertex graph $G$ in time $O(n^\omega)$, where $\omega < 2.376$ is the matrix multiplication exponent, and in $O(n^2)$ space by a result of Itai and Rodeh [1]. Basically, they show that $G$ contains a triangle if and only if $(A(G))^3$ has a non-zero entry on its main diagonal. Because a triangle is also a cycle $C_3$, one can use general cycle finding methods for detecting triangles. Alon, Yuster and Zwick show how triangles can be detected on an $m$-edge graph in $O(m^{2\omega/(\omega+1)}) = O(m^{1.41})$ time [6].
For a long time, the result of Nesetril and Poljak [2] was the best known; they showed the number of cliques of size $3k$ can be found in time $O(n^{\omega k})$ and $O(n^{2k})$ space. Finally, Eisenbrand and Grandoni [3] improved on the result of Nesetril and Poljak for a $(3k+1)$-clique and a $(3k+2)$-clique for small values of $k$. Specifically, they gave algorithms for finding cliques of size 4, 5, and 7 in time $O(n^{3.334})$, $O(n^{4.220})$, and $O(n^{5.714})$, respectively.
As far as I know, for general $k$, the problem of designing better algorithms is open. For possible consequences or complexity theoretic considerations, Downey and Fellows (see e.g. [4]) showed $k$-clique with parameter $k$ is $W[1]$-hard. The class $W[1]$ denotes the class of parameterized decision problems reducible to CLIQUE with parameterized reductions. It is believed that CLIQUE is not fixed-parameter tractable. There are hundreds of other problems known to be equivalent to CLIQUE under parameterized reductions. Furthermore, Feige and Kilian [5, Section 2] have a result saying that when $k$ is part of the input and $k \approx \log n$, then a polytime algorithm is not likely to exist.
If you consider some restricted graph classes, you can solve the problem in linear time on chordal graphs. Simply compute a clique tree of a chordal graph $G$ in $O(n+m)$ time, and then check if any clique is of size exactly $k$. On planar graphs, one can also find triangles in $O(n)$ time using the methods of [6].
[4] Downey, R. G., and Michael R. Fellows. "Fundamentals of Parameterized complexity." Undegraduate Texts in Computer Science, Springer-Verlag (2012).
