<p>Eppstein, Löffler, and Strash modified the Bron-Kerbosch algorithm, obtaining an algorithm that lists <a href="http://link.springer.com/chapter/10.1007/978-3-642-17517-6_36#page-1" rel="nofollow">all maximal cliques in $O(dn 3^{d/3})$ time</a>, where $d$ is the degeneracy of the graph (note $d \le \Delta$).</p>

<p>The same idea <a href="http://link.springer.com/article/10.1007/s11590-013-0698-2" rel="nofollow">can be extended for the maximum clique problem in $d$-degenerate graphs</a>, and the runtime can be improved to $O^*(2^{d/4})$.</p>

CC BY-SA 3.0
2013-07-12T17:07:33.700Z
2013-10-19T05:39:47.820Z
2013-10-19T05:39:47.820Z
Austin Buchanan
<p>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)</p>

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

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

CC BY-SA 3.0
2013-07-12T15:02:34.833Z
Don't you have $s\leq\Delta$?
Lamine
CC BY-SA 3.0
2013-07-12T15:54:39.080Z
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$.
Yixin Cao
CC BY-SA 3.0
2013-07-12T15:58:49.370Z
@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.
David Harris
<graph-algorithms>
Algorithms for finding clique in bounded-degree graph
David Harris
# Algorithms for finding clique in bounded-degree graph

(Asked by: username_0 on 2013-07-12)

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?

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: Don't you have $s\leq\Delta$?  
> **username_2**: 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$.  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_3 on 2013-07-12. Score: 14 | Accepted answer

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](http://link.springer.com/chapter/10.1007/978-3-642-17517-6_36#page-1), 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](http://link.springer.com/article/10.1007/s11590-013-0698-2), and the runtime can be improved to $O^\*(2^{d/4})$.


---

