Maximal Clique Finder

Pseudocode

Bron-Kerbosch explores with three sets: R is the clique built so far, P holds candidates that could still extend it, and X holds vertices already tried. A clique is maximal exactly when P and X are both empty.

BronKerbosch(R, P, X):
    if P and X are both empty:
        report R as a maximal clique
        return

    for each vertex v in P:
        BronKerbosch(R + {v},
                     P intersect neighbors(v),
                     X intersect neighbors(v))
        P = P - {v}
        X = X + {v}

// With pivoting: choose a pivot u from P union X and
// only branch on v in P that are NOT neighbors of u

X is the part people leave out, and without it the algorithm reports non-maximal cliques. When a vertex has already been explored at this level it moves into X, so any clique that could have included it is rejected as not maximal. The pivot refinement then cuts the branching factor sharply: every maximal clique must contain the pivot or one of its non-neighbours, so branching on the rest is wasted work.

Worked example, step by step

Enumerate all maximal cliques of a six-edge graph that contains two overlapping triangles and a pendant edge.

Example graph: Undirected edges A-B, A-C, B-C, B-D, C-D and D-E.

1. Start. R is empty, P holds all five vertices, X is empty. Branch on A first.
2. Branch on A. R becomes {A}. P narrows to the neighbours of A, which are B and C. Branching on B then C builds {A, B} and then {A, B, C}. At that point P and X are both empty, since D is not adjacent to A, so {A, B, C} is reported as maximal.
3. Branch on B, with A now in X. R becomes {B}. P narrows to C and D, since A has moved to X. Extending gives {B, C} and then {B, C, D}, because C and D are adjacent. P and X are empty there, so {B, C, D} is maximal.
4. Why {B, C} alone is not reported. When R is {B, C}, D is still in P, so the emptiness test fails and no clique is reported. This is the whole purpose of the test: {B, C} is a clique but not a maximal one, because it sits inside {A, B, C} and {B, C, D}.
5. The pendant edge. Branching down to D with A, B and C exhausted leaves E as the only candidate, giving {D, E}. E has no other neighbours, so this is maximal despite having only two vertices.

The maximal cliques are {A, B, C}, {B, C, D} and {D, E}. The maximum clique, meaning the largest one, has size 3 and there are two of them. Note that maximal and maximum are different: {D, E} is maximal because nothing can extend it, but it is far from maximum. Note too that B and C appear in two maximal cliques each, which is normal and is why the count of maximal cliques can be much larger than the vertex count.

Complexity, and where it comes from

Time: O(3^(V/3)) · Space: O(V^2)

The bound comes from the Moon-Moser theorem: a graph on V vertices can have at most 3 to the power V/3 maximal cliques, and that bound is tight, achieved by a complete multipartite graph of V/3 triangles. Since the algorithm must at minimum print every one of them, no enumeration algorithm can beat that in the worst case, and Bron-Kerbosch with pivoting matches it. This is worth internalising: the algorithm is optimal, but the problem itself is exponential. Finding just the single largest clique is NP-hard, and even approximating it within any reasonable factor is hard. In practice, pivoting and a degeneracy vertex ordering make sparse real-world graphs with tens of thousands of vertices tractable, because sparse graphs have far fewer maximal cliques than the worst case.

When to use Maximal Clique, and when not to

Decide first whether you want every maximal clique or just the biggest one, because they are different problems with different tools.

Common pitfalls

• Dropping the X set. Without X, the algorithm reports every clique rather than only the maximal ones, so {B, C} would appear alongside {A, B, C}. The output balloons and is wrong. X is what remembers that a branch has already been covered.
• Confusing maximal with maximum. A maximal clique cannot be extended; a maximum clique is the largest in the graph. {D, E} in the example is maximal and has size 2, while the maximum size is 3. Asking for "the maximal clique" is ambiguous and usually means the maximum one.
• Skipping the pivot on dense graphs. Plain Bron-Kerbosch without pivoting explores enormously more branches. On dense graphs the pivot is not an optimisation but the difference between finishing and not.
• Expecting polynomial behaviour. The number of maximal cliques can be exponential in the vertex count, so no implementation trick makes the general case fast. If a graph is dense and large, enumerate with a cap or reformulate the question.
• Treating self-loops or directions as meaningful. Cliques are defined on simple undirected graphs. Directed edges must be symmetrised first, and a decision made about whether a one-way edge counts as adjacency, because that choice changes the answer.

Frequently asked questions

What is a maximal clique?

A clique is a set of vertices that are all pairwise adjacent. A clique is maximal when no further vertex can be added while keeping that property. This is different from a maximum clique, which is the largest clique anywhere in the graph: every maximum clique is maximal, but a small maximal clique can exist alongside much larger ones.

How does the Bron-Kerbosch algorithm work?

It recurses on three sets: R, the clique built so far, P, the candidates that can still extend it, and X, the vertices already explored at this level. At each step it moves a candidate from P into R and restricts P and X to that vertex neighbours. When P and X are both empty, R is a maximal clique. Choosing a pivot and branching only on its non-neighbours prunes most of the search.

What is the difference between maximal and maximum clique?

Maximal means locally unextendable: you cannot add any vertex to it. Maximum means globally largest: no clique in the graph has more vertices. A graph can have many maximal cliques of different sizes, and finding all of them is a different problem from finding the single biggest one.

What is the time complexity of finding all maximal cliques?

O(3 to the power V/3) in the worst case, which is optimal. By the Moon-Moser theorem a graph can contain that many maximal cliques, so any algorithm that lists them all must take at least that long. On sparse graphs a degeneracy ordering gives a much better practical bound.

What are cliques used for?

Community detection in social networks, finding groups of co-expressed genes in bioinformatics, identifying sets of mutually compatible items in scheduling and recommendation, detecting fraud rings where all parties transact with each other, and matching problems where a clique represents a fully consistent set of choices.