liveBook · Manning

Excluded set X

As explained in Algorithms Every Programmer Should Know

The excluded set X contains vertices already processed in a Bron-Kerbosch search branch, preventing duplicate clique reports.

In the Bron–Kerbosch algorithm, X keeps track of vertices already explored in the current search branch. This history prevents the search from reporting the same maximal clique again. section 11.3 section 11.1

As the search explores a vertex:

  • Pass forward only vertices in X that are neighbors of the chosen vertex. section 11.1
  • After the recursive call returns, move the explored vertex from P into X. section 11.1
Figure 11.5 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.

See how a nonempty X stops the branch {2, 4} from reporting a clique already found as {1, 2, 4}. section 11.1

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines X and traces its neighbor intersection and update after recursion, focusing on duplicate tracking.
Examples
Traces branch {2, 4}, where X contains vertex 1 and blocks a repeat of {1, 2, 4}.
What you can do after
Apply excluded-set updates in a Bron–Kerbosch search to avoid reporting a maximal clique more than once.
How it connects
Connects X to the Bron–Kerbosch algorithm, maximal cliques, and candidate set P.

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.