# Algorithms for finding all cliques of a given degree in a graph

Consider a graph with $n$ vertices and maximum degree $Δ$. I would like to obtain all $s$ cliques, where $s≤Δ$ and both of them are small compared to $n$.

Bron-Kerbosch algorithm gives all maximal cliques but that's not quite what I need. I want all s cliques (where $s≤Δ$), including not maximal ones.

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

• Unless I'm mistaken, you can just replace if P and X are both empty: report R as a maximal clique by if |R|>= s: report R as a s-clique in BronKerbosch1 and it should work. And the other (more efficient) variants of the algorithm can probably be adapted too. Apr 11, 2017 at 13:30