# Bron-Kerbosch algorithm for finding cliques missing a few edges?

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.

• Augment your graph with $t$ edges and apply the Bron-Kerbosch algorithm as a blackbox. Commented Jun 17 at 10:04
• @codeR which $t$ of the $n \choose 2$ edges should be added? Commented Jun 17 at 10:29
• One trivial DP Algo has $\mathcal{O}(2^n)$ time complexity, which also gives all the $t$ values for all possible subgraphs
– EnEm
Commented Jun 17 at 11:14
• @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? Commented Jun 17 at 11:15
• @EnEm This was my first thought as well though it seems the augmentation idea might be a bit faster Commented Jun 17 at 11:16