5
$\begingroup$

Bron-Kerbosch is an algorithm to find maximal cliques in a undirected graph. In pseudocode it's the following (taken from wikipedia):

BronKerbosch1(R, P, X):
   if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
       P := P \ {v}
       X := X ⋃ {v}

I have read that the time complexity of some modified versions of this algorithm is $O(3^{n/3})$, but I can't seem to find the running time complexity of the simple version anywhere.

$\endgroup$
  • $\begingroup$ Yes I'm sorry, I asked the question without logging in and my edit needs to be peer reviewed before becoming visible. $\endgroup$ – XaitormanX Dec 30 '16 at 16:34
  • 1
    $\begingroup$ Consider a complete graph (with an edge between each pair of vertices). I expect you should be able to work out the running time. I suspect it will be something like $O(2^n)$, but try and work through it yourself, and if you can solve it, feel free to answer your own question. $\endgroup$ – D.W. Jan 2 '17 at 5:14
5
$\begingroup$

The exact running time of the algorithm depends on implementation details. The number of recursive calls to the procedure, however, is easily seen to be exactly the number of ordered cliques, that is, the number of ordered sequences of distinct vertices which form cliques. In particular, if the graph is complete then the number of recursive calls is $$ \sum_{k=0}^n n(n-1)\cdots(n-k+1) = \sum_{k=0}^n \frac{n!}{(n-k)!} = n! \sum_{k=0}^n \frac{1}{k!} \approx e \cdot n!. $$ When the maximum clique has size $k$, the number of recursive calls is at most $$ 1 + n + n(n-1) + \cdots + n(n-1)\cdots(n-k+1) \leq 2n^k. $$ Conversely, if you run the algorithm on a complete $k$-partite graph, then the number of recursive calls will be $\Omega(n^k)$.

$\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.