9.23

Idea
A clique is a set of vertices that are all pair-wise adjacent. A maximum clique is the largest such set.

The fastest exact technique in practice is a depth-first branch-and-bound based on the Bron–Kerbosch enumeration with pivoting, augmented with pruning by coloring (Tomita et al.). At every node we maintain: 1. R – vertices already chosen for the current clique, 2. P – candidates that can still be added (all adjacent to every v in R), 3. X – vertices already explored and therefore forbidden, and bound the search by an upper estimate of the best clique still reachable from P. The estimate is produced by greedy graph coloring: if the current best clique has size best and |R| + color(P) ≤ best, we stop exploring this branch.

Pseudocode

MAXCLIQUE(G): best ← ∅ BRONKERBOSCH(∅, V(G), ∅) return best BRONKERBOSCH(R, P, X): global best if P = X = ∅: if |R| > |best|: best ← R return u ← pivot from P ∪ X // choose vertex with most neighbours in P for v in P \ N(u): // Tomita pivoting if |R| + COLOR_BOUND(P) <= |best|: return // pruning BRONKERBOSCH(R ∪ {v}, P ∩ N(v), X ∩ N(v)) P ← P \ {v}; X ← X ∪ {v} COLOR_BOUND(P): c ← 0 U ← copy of P while U ≠ ∅: c ← c + 1 choose v ∈ U; remove v and all its neighbours from U return |R| + c

Reference Python 3 implementation

def max_clique(graph): n = len(graph) best = [] P = set(range(n)) def color_bound(P): bounds, U = 0, sorted(P, key=lambda v: -sum(graph[v])) while U: bounds += 1 v = U.pop() U = [u for u in U if not graph[v][u]] return bounds def expand(R, P, X): nonlocal best if not P and not X: if len(R) > len(best): best = R[:] return # Tomita pivot u = max(P | X, key=lambda v: len(P & neighbours[v])) if P or X else None for v in list(P - neighbours[u]): if len(R) + color_bound(P) <= len(best): return expand(R + [v], P & neighbours[v], X & neighbours[v]) P.remove(v) X.add(v) neighbours = [set(j for j in range(n) if graph[i][j]) for i in range(n)] expand([], P, set()) return best

Complexity
Worst-case time is O(3^n/3), but branch-and-bound with coloring is dramatically faster on real graphs. Space is O(n²) for the adjacency matrix plus recursion stack O(n).

How to use
Feed graph as a Boolean adjacency matrix; the function returns a list of vertex indices forming a maximum clique. Because it is exact, the first clique returned is guaranteed to be optimal.

Back to Chapter 9