8
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Don't you have $s\leq\Delta$? $\endgroup$ – Lamine Jul 12 '13 at 15:02
  • $\begingroup$ 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$. $\endgroup$ – Yixin Cao Jul 12 '13 at 15:54
  • $\begingroup$ @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. $\endgroup$ – David Harris Jul 12 '13 at 15:58
13
$\begingroup$

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, 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, and the runtime can be improved to $O^*(2^{d/4})$.

|cite|improve this answer
$\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.