Q:

Finding $k$-clique in a graph with running time of $|V|^{k-1}$

This is a homework problem. Let's say I have a graph $G$, how can I find a $k$-clique (i.e. a complete graph with $k$ vertices) inside $G$? So far I can think of a naive solution where I check if each node in k is connected to other nodes, and the running time would be $|V|^k$. How can I reduced it by $|V|$ to $|V|^{k-1}$?

A:

Nešetřil and Poljak give an algorithm running in time $O(n^{(\omega/3)k})$, for $k$ divisible by 3, which seems to be the state-of-the-art. This generalizes the well-known $O(n^\omega)$ algorithm for the case $k = 3$. Here $\omega$ is the matrix multiplication constant, currently known to be at most $2.373$, but conjectured to be $2$. See also Vassilevska (now Vassilevska-Williams), who gives an $o(n^k)$ algorithm which is space-efficient.

