Finding every maximal clique means exploring groups of vertices that are all connected to one another. The standard Bron–Kerbosch algorithm tries every candidate in P at each recursive step. In a dense graph, many candidates overlap, so that can create a lot of branching. Pivoting narrows the choices without losing maximal cliques. section 11.1
The search keeps three sets: R is the clique being built, P holds vertices that could still join it, and X holds vertices already explored. Choose a pivot from P ∪ X. Instead of branching on every vertex in P, branch only on vertices in P that are not neighbors of the pivot. Any maximal clique must include the pivot or a non-neighbor of it, so the other candidate branches are unnecessary. section 11.1 section 11.4
Listing 11.4 Pivot optimization
def _bron_kerbosch_with_pivot(self, R, P, X):
"""Optimized recursive backtracking using a pivot vertex."""
if not P and not X:
self.maximal_cliques.append(R)
return
pivot = next(iter(P.union(X)))
pivot_neighbors = self.graph[pivot] #A
for vertex in list(P.difference(pivot_neighbors)): #B
neighbors = self.graph[vertex]
new_R = R.union({vertex})
new_P = P.intersection(neighbors)
new_X = X.intersection(neighbors)
self._bron_kerbosch_with_pivot(new_R, new_P, new_X)
P.remove(vertex)
X.add(vertex)
def find_maximal_cliques(self):
"""Initializes the sets and starts the optimized algorithm."""
vertices = set(self.graph.keys())
self._bron_kerbosch_with_pivot(set(), vertices, set())
return self.maximal_cliques
return self.excess[sink]
The Python listing shows the change: choose a pivot from P ∪ X, then loop over P minus the pivot’s neighbors. The recursive updates to R, P, and X remain in place. section 11.1
What still counts as a result?
Pivoting changes which branches are tried, not when a clique is reported. A search can find {1, 2, 4} when both P and X become empty. If it later reaches {2, 4} with P empty but vertex 1 still in X, it reports nothing: that smaller clique was already covered. This is the X-set check, separate from pivoting’s reduction in branching. section 11.1
Pivoting is especially useful when dense graphs make the unoptimized search branch heavily. Its stated worst-case running time is O(3^(V/3)), matching the bound on how many maximal cliques a V-vertex graph can have; the stated space complexity is O(V). section 11.4
