Bron–Kerbosch Maximal Cliques
Follow R, P and X to find every maximal clique without confusing maximal with maximum.
By Riano · Published · Updated · Report a correction
Bron–Kerbosch Maximal Cliques
The Bron–Kerbosch algorithm is an efficient, recursive backtracking procedure to find all maximal cliques in an undirected graph. A clique is a subset of vertices such that every two distinct vertices in the subset are adjacent. A clique is maximal if it cannot be extended by including one more adjacent vertex—meaning it is inclusion-wise unextendible. This is distinct from a maximum clique, which simply refers to the clique(s) with the largest number of vertices.
The standard Bron–Kerbosch algorithm operates on three disjoint sets of vertices: R, P, and X.
- R (Current clique): Contains the vertices of the currently growing clique.
- P (Prospective candidates): Contains vertices that are connected to all vertices in R and can potentially be added to R to form a larger clique.
- X (Excluded vertices): Contains vertices that are connected to all vertices in R but have already been explored in a previous branch. This ensures that maximal cliques are not generated redundantly.
Worked Example
Consider a simple graph, a "Triangle and tail", consisting of vertices {0, 1, 2, 3} and edges {(0,1), (0,2), (1,2), (2,3)}. We initialize the algorithm with R = {}, P = {0, 1, 2, 3}, and X = {}.
The algorithm improves its efficiency using a pivot vertex u chosen from P ∪ X. Any maximal clique must contain either u or one of its non-neighbors. By picking a pivot u that maximizes the intersection size |P ∩ N(u)| (breaking ties with the lowest vertex ID), we minimize the number of recursive branches explored.
Initially, the algorithm selects a pivot, say u=0. Its neighbors are N(0) = {1, 2}. The algorithm branches on vertices in P that are not neighbors of 0, which are {0, 3}.
- Moving
0from P to R explores{0, 1, 2}. Trace calculation hitsP=∅, X=∅and reports expected result 0, 1, 2. - After backtracking,
0moves to X. The algorithm then branches on3, calculating expected result 2, 3.
When both P and X become empty at a certain recursion depth, the vertices in R form a maximal clique, and the algorithm records it.
Experiment
- Select "Triangle and tail" from the Graph dropdown.
- Click "Step" repeatedly to trace the algorithm and see the cliques discovered.
- Click "Finish" to jump to the final results and see the maximal clique count.
Open the full module in a new tab for a dedicated view of the enumeration steps.
Limitations
While the Bron–Kerbosch algorithm with pivoting is extremely effective in practice, the problem of listing all maximal cliques is inherently intractable for dense graphs. The number of maximal cliques in a graph with n vertices can grow exponentially, up to 3^(n/3) in the worst case (e.g., a Moon-Moser graph). Therefore, the algorithm's worst-case time complexity is O(3^(n/3)), meaning it is susceptible to combinatorial explosion and is strictly limited to finite, moderate-sized domains in real-time applications.
References
The Bron–Kerbosch algorithm is a classic combinatorial search procedure. For an implementation reference and further algorithmic details, see the NetworkX documentation:
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Bron–Kerbosch Maximal Cliques module.
Try Bron–Kerbosch Maximal Cliques on Riano →