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?

Improve this question
$\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, 2017 at 13:30

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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