The Bron-Kerbosch algorithm takes a graph and finds its maximal cliques in an efficient manner (as far as I'm aware, it is $O(3^{n/3})$, where $n$ is the number of vertices).

Let $t$ be a positive integer. I am interested in finding $t$-almost-cliques, that is, induced subgraphs which would be cliques if it wasn't for $t$ or fewer missing edges. Ideally I would like $t$ to depend the size of the almost-clique, but we can fix it for simplicity.

Is there a variant of the Bron-Kerbosch for $t$-almost cliques?

Even a reasonable algorithm would be appreciated.

  • $\begingroup$ Augment your graph with $t$ edges and apply the Bron-Kerbosch algorithm as a blackbox. $\endgroup$
    – codeR
    Commented Jun 17 at 10:04
  • $\begingroup$ @codeR which $t$ of the $n \choose 2$ edges should be added? $\endgroup$ Commented Jun 17 at 10:29
  • 2
    $\begingroup$ One trivial DP Algo has $\mathcal{O}(2^n)$ time complexity, which also gives all the $t$ values for all possible subgraphs $\endgroup$
    – EnEm
    Commented Jun 17 at 11:14
  • 1
    $\begingroup$ @codeR Thank you, that's helpful! Additional idea: in the case that $t$ depends on the size of the almost-clique, one can do this for $t=0,1,...,N$ and then filter out the cliques that are missing too many edges in the original graph. It seems to me that this should still be $O(n^{2N}3^{n/3})$, right? $\endgroup$ Commented Jun 17 at 11:15
  • 2
    $\begingroup$ @EnEm This was my first thought as well though it seems the augmentation idea might be a bit faster $\endgroup$ Commented Jun 17 at 11:16


Your Answer

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

Browse other questions tagged or ask your own question.