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?
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})$.