Skip to main content
1 of 3
Juan
  • 41
  • 2

What is the time complexity of the classic Bron-Kerbosch algorithm for finding cliques?

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

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 time complexity of the simple version anywhere. [1]: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm/ "wikipedia"

Juan
  • 41
  • 2