# Algorithms for finding clique in bounded-degree graph

Consider a graph with $n$ vertices and maximum degree $\Delta$. I would like to find if the graph has any $s$ cliques, where $s \leq \Delta$ and both of them are small compared to $n$. I only need to find a single such clique (or certify that none exist)

There is a straightforward way to do this: for each vertex $v$, test all $s$-subsets of the neighbors of $v$. The work is thus $\approx n \binom{\Delta}{s-1}$.

Are there any more efficient algorithms than this? Even achieving an exponential speed-up would be good?

• Don't you have $s\leq\Delta$? – Lamine Jul 12 '13 at 15:02
• A positive answer to this question will imply clique can be solved in $n^{o(s)}$ time. Note that $\Delta<n$. Or equivalently, consider solve the clique problem in $N[v]$ for each vertex $v$. – Yixin Cao Jul 12 '13 at 15:54
• @Yixin, I would be interested even in solutions that take time say $n \Delta^{c(s-1)}/(s-1)!$, where $c < 1$ is a constant. – David Harris Jul 12 '13 at 15:58

Eppstein, Löffler, and Strash modified the Bron-Kerbosch algorithm, obtaining an algorithm that lists all maximal cliques in $O(dn 3^{d/3})$ time, where $d$ is the degeneracy of the graph (note $d \le \Delta$).
The same idea can be extended for the maximum clique problem in $d$-degenerate graphs, and the runtime can be improved to $O^*(2^{d/4})$.