liveBook · Manning

Pivot vertex

As explained in Algorithms Every Programmer Should Know

A pivot vertex is a selected graph vertex used by the pivoting variant of Bron-Kerbosch to restrict which candidate vertices are explored.

A pivot vertex is selected from P or X to reduce branching in the pivoted Bron–Kerbosch algorithm. Rather than exploring every candidate in P, the algorithm explores only candidates that are not connected to the pivot. section 11.1

The pruning works because every maximal clique must either contain the pivot or include a vertex not connected to it:

  • Choose a pivot from P ∪ X, then iterate over its non-neighbors in P. section 11.1
  • Skipping the other candidates reduces redundant recursive calls, especially when dense graphs cause heavy branching. section 11.4

How Algorithms Every Programmer Should Know covers it

How deep it goes
Explains the pruning rationale and implementation rule, but does not compare pivot-selection strategies.
Examples
Shows a Python implementation that chooses from P ∪ X and iterates over the pivot's non-neighbors in P.
What it assumes
Assumes familiarity with Bron–Kerbosch's R, P, and X sets and the maximal-clique condition.
What you can do after
Apply pivoting in Bron–Kerbosch to skip candidates adjacent to the pivot while finding maximal cliques.
How it connects
Connects pivoting to Bron–Kerbosch, maximal cliques, and the candidate and explored sets P and X.

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.