11 Bron-Kerbosch Algorithm
This chapter covers
- Finding every maximal clique in a graph through recursive backtracking
- Tracking candidate, excluded, and clique sets to avoid exploring the same group
- Analyzing time and space complexity with algorithmic insights
In the previous chapter, we worked through the Push-Relabel algorithm that computes the maximum flow by having the nodes push excess flow to their neighbors and raise their own height when they get stuck. A few real-world applications of Push-Relabel discussed were baseball eliminations in tournaments where a small network is developed from the team tested. Further, many graph libraries, like the Boost library in C++ and NetworkX in Python, utilize the maximum flow network concept and its variations too. Now, instead of asking how much can flow from one point to another, we ask which group of nodes are mutually connected to each other, thus moving from maximum flow into graph clustering.
The Bron–Kerbosch algorithm, first published in 1973, solves graph clustering with the same backtracking approach, try to grow a group, back out when you can't, and never waste time revisiting ground you've already covered. We'll trace its recursion step by step, seeing how it uses three sets, the clique being built, the candidates still allowed to join it, and the nodes already ruled out, to guarantee every maximal clique is found exactly once.