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?

  • $\begingroup$ Don't you have $s\leq\Delta$? $\endgroup$
    – Lamine
    Commented Jul 12, 2013 at 15:02
  • $\begingroup$ 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$. $\endgroup$
    – Yixin Cao
    Commented Jul 12, 2013 at 15:54
  • $\begingroup$ @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. $\endgroup$ Commented Jul 12, 2013 at 15:58

1 Answer 1


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.