2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – xavierm02
    Apr 11 '17 at 13:30
1
$\begingroup$

This maybe: https://papers-gamma.link/paper/32
With an open source implementation here: https://github.com/maxdan94/kClist

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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