Bron–Kerbosch Algorithm

Bron–Kerbosch algorithm is a recursive backtracking enumeration algorithm in computation and algorithms for finding all maximal cliques in an undirected graph G = (V, E). Published in 1973 by Dutch computer scientists Coen Bron and Joep Kerbosch as Algorithm 457 in Communications of the ACM, the algorithm maintains three pairwise disjoint vertex subsets (R, P, X) across recursive calls to avoid generating duplicate cliques or expanding non-maximal subgraphs.

Although deciding whether a graph contains a clique of size k is NP-complete within computational complexity theory (and not directly solvable in polynomial time via standard dynamic programming unless treewidth is bounded) and an n-vertex graph can possess up to 3^n/3 maximal cliques (the Moon–Moser bound, achieved by a disjoint union of n/3 triangles), Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi proved in 2006 that the Bron–Kerbosch algorithm with pivoting runs in worst-case O(3^n/3) time—matching the theoretical maximum possible output size without any polynomial overhead factor. Furthermore, when combined with an outer degeneracy ordering (Eppstein, Löffler, and Strash, 2010) and prefix-tree (trie) or bitset neighborhood intersections, the algorithm runs in O(d n 3^d/3) parameterized time on sparse graphs of degeneracy d, making it the standard engine for clique enumeration in biological and social network analysis.

Cliques, Maximal Cliques, and the Moon–Moser Theorem

Let G = (V, E) be a simple undirected graph with vertex count n = |V| and edge count m = |E|. For any vertex v ∈ V, denote its open neighborhood by N(v) = {u ∈ V : {u, v} ∈ E}.

• A clique C ⊆ V is a subset of pairwise adjacent vertices ({u, v} ∈ E for all distinct u, v ∈ C).
• A maximal clique is a clique C that cannot be extended by adding any further vertex from V \ C (that is, there is no w ∈ V \ C such that C ⊆ N(w)).
• A maximum clique is a maximal clique of largest possible cardinality ω(G) across the entire graph.

In 1965, John W. Moon and Leo Moser proved that any undirected graph on n vertices contains at most 3^n/3 maximal cliques (more precisely, 3^n/3 when n ≡ 0 mod 3; 4 · 3^{⌊n/3⌋−1} when n ≡ 1 mod 3; and 2 · 3^⌊n/3⌋ when n ≡ 2 mod 3). Consequently, any algorithm that explicitly lists all maximal cliques requires Ω(3^n/3) worst-case time in the size of the output.

The Three Disjoint Vertex Sets (R, P, X)

Each recursive invocation of BronKerbosch(R, P, X) maintains three disjoint vertex sets whose roles partition the current search subtree:

1. Current Clique (R): The subset of vertices already committed to the partially constructed clique. Every vertex in P ∪ X is adjacent to every vertex in R:

1. Candidate Set (P): Prospective vertices that are adjacent to all vertices in R and have not yet been explored as extensions of R.
2. Excluded Set (X): Vertices that are also adjacent to all vertices in R, but have already been fully processed in earlier branches at the current recursion depth. Any maximal clique containing R and at least one vertex from X has already been output by an earlier recursive call.

This invariant yields a clean two-part base condition:

• Maximal Clique Found (P = ∅ and X = ∅): No vertex in V \ R is adjacent to all of R, so R is reported as a maximal clique.
• Dead-End Backtrack (P = ∅ and X ≠ ∅): Although R cannot be extended using P, every element x ∈ X is adjacent to all of R, proving that R is not maximal (and its maximal extensions through X were already enumerated). The branch backtracks without output.

Version 1: Basic Bron–Kerbosch Without Pivoting

At the root call, R = ∅, P = V, and X = ∅. While P ≠ ∅, the basic algorithm selects a vertex v ∈ P, makes the recursive call

and upon return moves v from the candidate set to the excluded set: P ← P \ {v} and X ← X ∪ {v}. While simple, Version 1 makes a recursive call for every vertex in P even when those calls are doomed to end with P′ = ∅ and X′ ≠ ∅.

Version 2: Pivoting Strategy and the O(3^(n/3)) Bound

To prune non-maximal branches before recursing, Bron and Kerbosch introduced a pivot vertex u ∈ P ∪ X. Observe that for any maximal clique C extending R, either:

1. C contains the pivot vertex u itself (if u ∈ P), or
2. C does not contain u, in which case C must contain at least one vertex v ∈ P \ N(u) that is non-adjacent to u (otherwise u could be added to C, contradicting maximality of C).

Therefore, at the current recursion node, it suffices to iterate and branch only over vertices v ∈ P \ N(u):

1. If P = ∅ and X = ∅, report R as a maximal clique and return.
2. Choose a pivot u ∈ P ∪ X that maximizes |P ∩ N(u)| (the Tomita–Tanaka–Takahashi rule, which minimizes the number of remaining branches |P \ N(u)|).
3. For each vertex v ∈ P \ N(u):
   • Call BronKerbosch2(R ∪ {v}, P ∩ N(v), X ∩ N(v)).
   • Update P ← P \ {v} and X ← X ∪ {v}.

Using recurrence analysis on T(|P|) = max_k (k · T(|P| − k)), Tomita et al. (2006) proved that choosing u ∈ P ∪ X to maximize |P ∩ N(u)| bounds the total time of BronKerbosch2 by O(3^n/3), which is worst-case optimal across all n-vertex graphs.

Version 3: Degeneracy Ordering for Sparse Graphs

Real-world biological and information networks are typically sparse, characterized by a small degeneracy d—the smallest integer d such that every nonempty subgraph contains a vertex of degree at most d (computable in O(n + m) linear time by repeatedly removing minimum-degree vertices, Matula and Beck 1983). In BronKerbosch3 (Eppstein, Löffler, and Strash, 2010), the outer loop orders V = (v₁, v₂, …, v_n) in a degeneracy ordering and for each v_i invokes the pivoted BronKerbosch2 with:

• R = {v_i},
• P = N(v_i) ∩ {v_i+1, …, v_n} (which has size |P| ≤ d by definition of degeneracy),
• X = N(v_i) ∩ {v₁, …, v_i−1}.

Because every inner pivoted search starts with |P| ≤ d, each inner recursion tree has size at most O(3^d/3), yielding a parameterized worst-case running time of O(d n 3^d/3).

1. Chemoinformatics and 3D Pharmacophore Matching (Gardiner et al., 1997): Finding the Maximum Common Induced Subgraph (MCIS) between two chemical molecular graphs G₁ and G₂ reduces via Levi's modular product graph G₁ ⊡ G₂ to enumerating maximal cliques with the Bron–Kerbosch algorithm; this is standard in drug discovery and ligand docking.
2. Protein–Protein Interaction (PPI) Complex Detection and Structural Alignment: In systems biology, Clique Percolation Method (CPM) and DALI/VAST protein structure comparison tools apply pivoted Bron–Kerbosch to detect overlapping multi-protein complexes and conserved 3D secondary-structure cores.
3. Genomic Haplotype Phasing and Overlap-Layout-Consensus Assembly: Compatibility graphs of sequencing reads and single-nucleotide variants use maximal clique enumeration (alongside De Bruijn graph paths) to cluster reads originating from identical viral quasispecies strains or polyploid haplotypes.

Why must the pivot vertex u be chosen from P ∪ X rather than from P alone?

A vertex x ∈ X can be adjacent to most or all vertices remaining in P. Allowing u ∈ X to serve as the pivot lets the algorithm immediately prune all of u's neighbors in P (P ∩ N(u)); if x ∈ X is adjacent to every vertex in P, then P \ N(x) = ∅ and the branch terminates in zero recursive calls.

How can bitsets accelerate the Bron–Kerbosch algorithm?

In dense graphs or inside the small d-bounded subproblems created by degeneracy ordering, representing P, X, and each vertex's neighborhood N(v) as 64-bit machine words allows set intersections (P ∩ N(v)) and population counts (for pivot selection) to execute via single-cycle bitwise AND and hardware popcount instructions.

1. Bron, C., & Kerbosch, J. (1973). "Algorithm 457: Finding all cliques of an undirected graph." Communications of the ACM, 16(9), 575–577. https://doi.org/10.1145/362342.362367
2. Moon, J. W., & Moser, L. (1965). "On cliques in graphs." Israel Journal of Mathematics, 3(1), 23–28. https://doi.org/10.1007/BF02760024
3. Tomita, E., Tanaka, A., & Takahashi, H. (2006). "The worst-case time complexity for generating all maximal cliques and computational experiments." Theoretical Computer Science, 363(1), 28–42. https://doi.org/10.1016/j.tcs.2006.06.015
4. Eppstein, D., Löffler, M., & Strash, D. (2010). "Listing all maximal cliques in sparse graphs in near-optimal time." In Algorithms and Computation (ISAAC 2010) (pp. 403–414). Springer. https://doi.org/10.1007/978-3-642-17517-6_36