<p>This maybe: <a href="https://papers-gamma.link/paper/32" rel="nofollow noreferrer">https://papers-gamma.link/paper/32</a><br />
With an open source implementation here: <a href="https://github.com/maxdan94/kClist" rel="nofollow noreferrer">https://github.com/maxdan94/kClist</a></p>

CC BY-SA 4.0
2020-12-31T13:07:13.103Z
2020-12-31T13:07:13.103Z
maxdan94
<p>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$. </p>

<p>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.</p>

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

CC BY-SA 3.0
2017-04-11T13:30:25.093Z
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](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm) and it should work. And the other (more efficient) variants of the algorithm can probably be adapted too.
xavierm02
<graph-algorithms><clique>
Algorithms for finding all cliques of a given degree in a graph
AbdelKh
# Algorithms for finding all cliques of a given degree in a graph

(Asked by: username_0 on 2017-04-11)

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?

**Tags:** graph-algorithms, clique

> **Comments:**
> **username_1**: 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](https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm) and it should work. And the other (more efficient) variants of the algorithm can probably be adapted too.  

---

## 1 answers

### Answer by username_2 on 2020-12-31. Score: 1

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


---

