Bron-Kerbosch Algorithm

Purpose: Enumerate all maximal cliques of an undirected graph. With pivoting, it runs in $O (3^{n /3})$ — which is optimal, because a graph can have that many maximal cliques (Moon-Moser).

Algorithm

Recursive backtracking on three sets:

$R$ — the clique built so far,
$P$ — candidates that can still extend $R$ ,
$X$ — vertices already processed (used to avoid reporting the same clique twice).

BronKerbosch(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
    choose a pivot u from P ∪ X maximising |P ∩ N(u)|
    for each v in P \ N(u):
        BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v))
        P ← P \ {v}
        X ← X ∪ {v}

Why the pivot. Any maximal clique must contain either $u$ or a vertex not adjacent to $u$ . So it suffices to branch on $P ∖ N (u)$ , and choosing $u$ to maximise $∣ P \cap N (u) ∣$ makes that set as small as possible. Without pivoting the algorithm still works but is dramatically slower.

Code

Bitset version — the one to use, since all set operations become single machine words:

int n;
vector<unsigned long long> adj;   // adj[v] = bitmask of neighbours (n <= 64)
vector<unsigned long long> cliques;
 
void bk(unsigned long long R, unsigned long long P, unsigned long long X) {
    if (!P && !X) { cliques.push_back(R); return; }
 
    // pivot: vertex of P|X with the most neighbours inside P
    int pivot = -1, best = -1;
    unsigned long long PX = P | X;
    for (unsigned long long t = PX; t; t &= t - 1) {
        int u = __builtin_ctzll(t);
        int c = __builtin_popcountll(P & adj[u]);
        if (c > best) { best = c; pivot = u; }
    }
 
    unsigned long long cand = P & ~adj[pivot];
    for (unsigned long long t = cand; t; t &= t - 1) {
        int v = __builtin_ctzll(t);
        bk(R | (1ULL << v), P & adj[v], X & adj[v]);
        P &= ~(1ULL << v);
        X |= (1ULL << v);
    }
}

Paradigm

Backtracking with pruning. $X$ prunes duplicates; the pivot prunes branches.

Complexity

Time: $O (3^{n /3})$ worst case with pivoting — matching the maximum possible number of maximal cliques
With a degeneracy ordering at the top level: $O (d n 3^{d /3})$ where $d$ is the graph degeneracy — near-linear on sparse real-world graphs
Space: $O (n^{2} /64)$ for the adjacency bitsets, $O (n)$ recursion depth

Correctness

Every reported $R$ is a clique by construction (each added $v$ is adjacent to all of $R$ ). It is maximal because $P \cup X = \emptyset$ means no vertex is adjacent to all of $R$ . No clique is reported twice: once $v$ moves from $P$ to $X$ , any later branch containing $v$ hits a non-empty $X$ at its would-be reporting point and is suppressed. Completeness follows from the pivot argument above. ∎

Variants / Use Cases

Maximum clique — take the largest reported clique, or use a dedicated branch-and-bound solver with a colouring bound (much faster when you only need the maximum)
Maximum independent set — run on the complement graph
Minimum vertex cover — $n$ minus the maximum independent set (König’s theorem gives a flow solution in bipartite graphs)
Graph colouring lower bounds — the clique number bounds the chromatic number from below
Community detection / social network analysis — the original motivation for degeneracy-ordered Bron-Kerbosch
Maximum Clique and Independent Set — the topic page

whoashish's cp notes

Directory