liveBook · Manning

Pivoting

As explained in Algorithms Every Programmer Should Know

Pivoting selects a pivot element to restrict branching and reduce redundant work during a search.

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

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains the pivot choice and branching rule, then shows their placement in a Python recursive implementation.
Examples
Shows a Python pivot-optimization listing alongside graph traces that distinguish a new maximal clique from an already-covered subset.
What it assumes
Defines cliques and the roles of R, P, and X before introducing pivoting; assumes familiarity with sets and recursive search.
What you can do after
Build it from scratch by branching over P minus the pivot’s neighbors in a recursive Bron–Kerbosch search.
How it connects
Connects pivoting to maximal cliques, graph neighbors, recursive backtracking, and the Bron–Kerbosch P and X sets.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.