11 Bron-Kerbosch Algorithm

The chapter introduces the Bron–Kerbosch algorithm as a way to find all maximal cliques in an undirected graph, shifting from flow problems to graph clustering. A clique is a set of vertices where every vertex is directly connected to every other vertex, and a maximal clique is one that cannot be extended by adding any more vertices. The chapter motivates this with practical needs such as identifying tightly connected user groups, where brute force is far too expensive because it would require checking every subset of vertices.

The core of the algorithm is a recursive backtracking search that maintains three sets: R for the clique currently being built, P for candidate vertices that can still be added, and X for vertices already explored so the same clique is not reported twice. At each step, a vertex is moved from P into R, and the algorithm intersects the candidate and excluded sets with that vertex’s neighbors to preserve only vertices that remain compatible with the growing clique. When both P and X are empty, the current set R is guaranteed to be maximal. The chapter walks through a full example to show how this process finds maximal cliques while pruning duplicate or dead-end branches.

The chapter also explains why the algorithm is effective in practice and how it is optimized. The pivoting improvement reduces branching by choosing a pivot vertex and only exploring candidates not connected to it, which can greatly cut down unnecessary recursion while preserving correctness. With this optimization, the algorithm matches the theoretical worst-case limit on the number of maximal cliques, making it optimal for output-sensitive enumeration, and it uses only linear extra space for the recursion stack. Finally, the chapter highlights applications in stereo vision, molecular similarity and drug design, and graph libraries such as NetworkX and igraph, where Bron–Kerbosch is used as a standard clique-finding engine.

The left diagram shows every one of the five vertices connects directly to all 4 others, so all possible 10 edges are present, making it a clique. On the other side, we have a missing edge from vertex 2 to 3, which is enough to disqualify the whole group, so it is not a valid clique.

The example graph and three sets, R, P, and X. R, the clique being built so far (all mutually connected), P, the candidates still connected to everything in R and therefore still eligible to join it, and X, the vertices already fully explored, kept around only so the algorithm never reports the same maximal clique twice. The initial call starts with R and X empty and P holding every vertex in the graph.

Recursive trace of Branch 1 on the full network. The algorithm progressively locks nodes 1, 2, and 4 into R, pruning prospective candidates in P via neighbor intersections until both P and X are empty, confirming maximal clique {1, 2, 4}.

Backtracking to the top level and starting the second branch. With the {1, 2, 4} branch closed out, the recursion unwinds to the root call and tries vertex 2 next. Vertex 1 already fully explored moves into X instead of disappearing, and the new P and X are computed by intersecting the old sets with vertex 2's neighbors, so only vertices still compatible with the growing clique carry forward.

A branch that closes without producing a new clique. Extending R to {2, 4} empties P, but X still holds vertex 1. A non-empty X at this point means {2, 4} is only a subset of a clique already found on an earlier branch ({1, 2, 4}) so the recursion backtracks here without reporting anything.

Finding the second maximal clique. Backtracking again and trying vertex 3, then vertex 5, grows R to {2, 3, 5}. This time P and X both empty out together, confirming a genuinely new maximal clique distinct from the first.

• A clique is a subset of vertices in an undirected graph where every distinct pair of vertices is connected by a direct edge, forming a complete subgraph.
• A maximal clique is a complete subgraph that cannot be extended by adding any additional vertices without breaking the completeness property.
• Finding maximal cliques is essential for identifying highly cohesive and isolated communities within massive, noisy networks.
• The naive brute force approach requires generating the entire power set of vertices, resulting in an impossible time complexity of O(n2 x 2n).
• The Bron-Kerbosch algorithm solves this problem using a highly optimized recursive backtracking architecture.
• The algorithm builds cliques vertex by vertex, exploring paths depth-first to minimize the operational memory footprint.
• It utilizes three distinct state sets during recursion: R (the current clique), P (the prospective vertices), and X (the excluded vertices).
• Set R acts as the accumulator, safely storing the mutually connected vertices as the recursion traverses deeper into the graph.
• Set P restricts the search space dynamically. At each step, it is strictly intersected with the neighbors of the most recently added vertex.
• Set X serves as a historical filter. It tracks vertices that have already been fully explored, allowing the algorithm to instantly prune branches that would result in duplicate cliques.
• A valid maximal clique is successfully identified and recorded only when both set P and set X become completely empty simultaneously.
• If set P becomes empty but set X contains elements, the algorithm recognizes the current clique R is merely a sub-clique of a previously discovered maximal clique and discards it.
• The standard algorithm suffers from excessive recursive branching on dense graphs because it iterates over every single vertex in the prospective set P.
• The pivoting optimization dramatically reduces recursive branching by selecting a pivot vertex from the union of P and X.
• Because any maximal clique must contain either the pivot itself or at least one non-neighbor of the pivot, the algorithm only needs to iterate over the non-neighbors of the chosen pivot.
• The maximum theoretical number of maximal cliques in a graph is bounded by 3V/3, as proven by Moon and Moser.
• The optimized Bron-Kerbosch algorithm operates exactly at this theoretical limit, achieving an optimal worst-case time complexity of O(3V/3).
• The space complexity of the algorithm is highly efficient at O(V), as it only requires memory proportional to the maximum depth of the recursive call stack.

1. Code implementation: https://github.com/aniketwattamwar/Algorithms-Every-Programmer-Should-Know
2. Video Explanation: Bron-Kerbosch Algorithm | Explanation with Example
3. NetworkX, find_cliques documentation: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.clique.find_cliques.html
4. Horaud, R. and Skordas, T. "Stereo Correspondence Through Feature Grouping and Maximal Cliques." IEEE Transactions on Pattern Analysis and Machine Intelligence, 1989. https://ieeexplore.ieee.org/document/42855/
5. Raymond, J.W. and Willett, P. "RASCAL: Calculation of Graph Similarity using Maximum Common Edge Subgraphs." The Computer Journal, 45(6), 2002. https://academic.oup.com/comjnl/article/45/6/631/429187
6. "Clique-Detection Algorithms for Matching Three-Dimensional Molecular Structures." https://www.sciencedirect.com/science/article/abs/pii/S1093326397000892

FAQ