BronKerbosch

The Bron–Kerbosch algorithm is a recursive backtracking method for enumerating all maximal cliques in an undirected graph. Introduced by Bron and Kerbosch in 1973, it remains a foundational technique in graph theory and network analysis.

During execution, the algorithm maintains three sets: R (the current clique), P (vertices that can extend R), and X (vertices that should be excluded to avoid duplicates). If P and X are empty, R is a maximal clique. Otherwise, the algorithm selects a pivot and recurses with R ∪ {v}, P ∩ N(v), and X ∩ N(v) for eligible vertices v, while updating P to P \ {v} and X to X ∪ {v}. A common optimization selects a pivot u from P ∪ X and iterates only over P ∩ N(u) to minimize redundant exploration.

Variants and improvements include pivoting strategies, degeneracy ordering (notably in Tomita et al.), and bitset-based implementations that speed up set operations. These refinements have made Bron–Kerbosch practical for larger graphs and for applications requiring enumeration of all maximal cliques rather than just a single one.

Complexity and applications: in the worst case, runtime is exponential in the number of vertices, and the number of maximal cliques can also grow exponentially. The algorithm is widely used in network analysis, bioinformatics, chemistry, and related fields to identify tightly connected subgraphs, communities, motifs, or common substructures.

See also: MCQ algorithm, Tomita variants, maximal clique problem.