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\setminus 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(dn{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=\varnothing$ 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