liveBook · Manning

Maximal clique problem

As explained in Algorithms Every Programmer Should Know

A maximal clique is a clique that cannot be enlarged by adding another vertex while preserving pairwise adjacency.

Suppose you want to find groups of users in which everyone is directly connected to everyone else. Each such group is a clique. A maximal clique goes one step further: no additional vertex can join without breaking that all-to-all connection. “Maximal” does not mean “largest in the graph.” It means the group cannot be extended. section 11.1

Why a connected pair may not be an answer

In the example graph, {1, 2, 4} is a maximal clique. Although {2, 4} is also a clique, vertex 1 can join it, so {2, 4} is not maximal. Another maximal clique, {2, 3, 5}, overlaps the first at vertex 2. The task is to find every group that cannot grow, not just one large group. section 11.1

Bron–Kerbosch finds these groups by growing a clique and backtracking when a branch is finished:

  • Keep three sets: R is the clique under construction, P holds vertices still eligible to join, and X holds vertices already explored. section 11.1
  • Choose a vertex from P and add it to R. Intersect P and X with that vertex’s neighbors so the next branch retains only compatible vertices. section 11.1
  • Report R only when both P and X are empty. If P is empty but X is not, do not report it: an earlier branch already accounted for a larger clique. section 11.4
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.

Follow the branch ending at {2, 4}: P is empty, but vertex 1 remains in X. That single excluded vertex shows why the branch must not produce another answer. section 11.1

Checking every subset by brute force becomes impractical as the graph grows. Bron–Kerbosch narrows each branch with neighbor intersections; a pivot can reduce branching further by limiting which candidates are tried. Maximal-clique finding also applies beyond social groups: in stereo vision, a compatibility graph connects candidate feature matches that can coexist, letting a search identify mutually consistent groups of matches. section 11.4 section 11.2

How Algorithms Every Programmer Should Know covers it

How deep it goes
Defines maximality and works through recursive search, termination, Python implementation, and pivoting rather than stopping at the graph-theory term.
Examples
Traces two overlapping maximal cliques and a rejected sub-clique, then describes compatible feature matches across two camera views.
What it assumes
Starts with undirected vertices and edges, defining cliques before explaining maximality and recursive search.
What you can do after
Build it from scratch with Python sets and Bron–Kerbosch backtracking to enumerate maximal cliques without reporting explored sub-cliques.
How it connects
Connects cliques to recursive backtracking, graph clustering, pivoting, compatibility graphs, and stereo correspondence.

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.