The Graph Isomorphism Problem

Two graphs are isomorphic if one can be relabelled into the other: the same connections, different names on the dots. Deciding whether any two given graphs are isomorphic is easy to state, and an answer is easy to check. It is also one of the very few natural problems that complexity theory has never managed to file in either of its usual drawers.

What a graph is, and what isomorphism means

A graph is just dots and lines: vertices and edges. The drawing carries no information of its own, because where you put a vertex on the page is your choice rather than a property of the graph. So the same graph can be drawn twice and produce two pictures that look nothing like each other.

Take a square, with corners 1, 2, 3, 4 and edges running round the outside. Now put four dots in a row, W X Y Z, and join W to X, X to Y, Y to Z, and Z back to W. One picture is a box. The other is a zigzag with a long line looping back to the start. They are the same graph, and the relabelling 1 to W, 2 to X, 3 to Y, 4 to Z carries every edge onto an edge and every gap onto a gap.

That is what an isomorphism is: a one-to-one pairing of the vertices of one graph with the vertices of the other, such that two vertices are joined in the first exactly when their partners are joined in the second. Both directions matter. A pairing that puts all the edges in the right place but invents an extra one does not count.

What the demo makes obvious

The demo above gives you eight vertices, twelve edges, and two drawings of the same object. Pair a number with a letter and the readout re-examines every matched pair of vertices at once. A complete mapping needs 28 comparisons, and they finish before your finger leaves the mouse. That is the cheap half.

The expensive half is the part you do by hand: hunting for a correspondence that survives all 28 checks simultaneously. Eight vertices allow 8 factorial, or 40,320, possible pairings, which a computer would grind through instantly. Go to thirty vertices and the count passes 2.6 x 10^32, at which point brute force stops being an option. Nobody has a general method that reliably avoids something like that search.

Flip the “make them different” toggle and the two graphs stop being twins, so no amount of rearranging will win. Ask the demo to reveal a mapping in that mode and it does something worth pausing on. It compares degree sequences, the sorted list of how many edges meet each vertex. Relabelling cannot change how many neighbours a vertex has, so isomorphic graphs must agree on that list, and when the lists differ you have proved non-isomorphism in a few dozen operations without searching at all. When they agree you have learned almost nothing, and the search is still ahead of you. The same lopsidedness shows up in the serious algorithms, which spend nearly all their effort on the cases where the cheap tests come back inconclusive.

Neither in P, nor NP-complete

Graph isomorphism sits in NP, which the demo makes easy to see: hand over a candidate mapping and it can be checked in polynomial time. So P vs NP governs the outer limits of the problem. What makes graph isomorphism unusual is where it sits inside those limits.

Almost every natural problem in NP has been sorted into one of two piles. Either someone found a polynomial-time algorithm, which puts it in P, or someone proved it NP-complete, which makes it as hard as everything else in NP. Sorting and primality testing went into the first pile. The travelling salesman problem and SAT went into the second, along with thousands of others. Graph isomorphism has resisted both piles for over fifty years.

Richard Ladner proved in 1975 that this middle ground is not empty. If P and NP really are different, then there must exist problems in NP that are neither in P nor NP-complete, a class usually called NP-intermediate. Ladner’s proof is a construction, though, and the problems it builds are artificial, assembled by diagonalisation for the express purpose of landing in the gap. Nobody wanted to solve them. Graph isomorphism is one of a small handful of candidates that people actually care about, alongside integer factoring.

There is decent evidence that it is not NP-complete. In 1987 Uwe Schöning showed that graph isomorphism lies in the low hierarchy of NP, and that has a sharp consequence: if the problem were NP-complete, the polynomial hierarchy would collapse to its second level. Complexity theorists treat that collapse as very unlikely, so most of them expect graph isomorphism is not NP-complete. That is an expectation rather than a proof, and nobody has ruled NP-completeness out.

Richard Karp noticed the awkwardness at the very beginning. His 1972 paper established twenty-one problems as NP-complete and set the template for the field, and graph isomorphism was not among them. Looking back on the work, Karp wrote that he had been “frustrated by my inability to classify linear programming, graph isomorphism and primality”. Linear programming fell to Khachiyan in 1979. Primality fell to Agrawal, Kayal and Saxena in 2002. Graph isomorphism is still sitting where Karp left it.

Where it actually matters

The problem is not a curiosity kept alive by theorists. Chemistry leans on it hardest, because a molecule is a graph with atoms for vertices and bonds for edges, so asking whether a newly synthesised compound is already in the database is an isomorphism query. Registries such as CAS run millions of them. Chip designers do the same thing under the name layout versus schematic, checking that the transistor network etched onto silicon really is the circuit the engineer drew. Computer vision uses it to match a scene against a stored model, and network analysts use it to find repeated substructures in social and biological graphs.

Easy in practice, unsolved in theory

Ask a chemist or a chip designer whether graph isomorphism is hard and you will get a puzzled look. In practice it is solved. Programs such as nauty, written by Brendan McKay from 1981 onwards, and Adolfo Piperno’s Traces, along with VF2, saucy, Bliss and conauto, dispose of graphs with thousands of vertices in well under a second. McKay and Piperno’s 2014 paper in the Journal of Symbolic Computation is the standard account of how.

They work by refinement. Colour every vertex by its degree, then repeatedly re-colour each vertex according to the multiset of colours around it. Vertices that end up with different colours can never be paired, and after a few rounds the colour classes are usually small enough that a short search finishes the job. This procedure is the one-dimensional Weisfeiler-Leman algorithm, and some version of it sits inside every competitive solver. On a random graph it shatters the vertices into singletons almost immediately.

This gap between practice and theory is real, and it is not a sign that the theorists have missed something obvious. Refinement has known blind spots, and they can be aimed at deliberately. Regular graphs defeat the first round outright, since every vertex has the same degree and therefore gets the same colour. In 1992 Cai, Fürer and Immerman built pairs of non-isomorphic graphs that defeat the k-dimensional version of the algorithm for any fixed k you choose in advance. Miyazaki adapted that construction in 1996 to produce graphs on which nauty itself runs in exponential time. Strongly regular graphs give solvers similar trouble, and so do the Paulus graphs. Every one of these families had to be engineered, and none of them turns up in a molecule database by accident, which is how the practical story and the theoretical story can both be true at once.

The error and the repair

On 10 November 2015, at a seminar in Chicago, László Babai announced an algorithm running in quasipolynomial time: roughly 2 raised to a power of log n, rather than a power of n. The previous record, set by Babai and Eugene Luks in 1983, had stood for thirty-two years at exp(O(sqrt(n log n))). Quasipolynomial is not polynomial, but it is enormously closer to it than anything before. The paper went up on arXiv on 11 December 2015, with a revised version following on 19 January 2016.

Then, on 4 January 2017, Babai announced that Harald Helfgott had found an error. Helfgott had been working through the proof line by line while preparing a talk on it for the Bourbaki seminar in Paris, and he caught a flaw in the analysis of a routine called Split-or-Johnson. The quasipolynomial claim was withdrawn. The algorithm still worked, and the weaker subexponential bound still beat the 1983 record, but the headline result was gone.

It came back within the week. Babai found a replacement for the offending recursive call on 7 January, a few lines of pseudocode justified by a new lemma about the structure of coherent configurations. On 9 January he posted an update restoring the claim, with the parenthetical “now really”, and gave a talk at Georgia Tech the same day. On 14 January Helfgott confirmed the repair from the podium at the Bourbaki seminar, the very talk that had exposed the error in the first place. He later showed the exponent can be taken as 3, giving a running time of 2 to the power O((log n)^3). The whole sequence played out in public, on blogs and seminar slides, over ten days, and the result has stood since.

What is still open

Babai’s algorithm did not settle anything. Quasipolynomial time is a ceiling rather than a classification, and the problem is roughly where Karp left it in 1972: not known to be in P, and not known to be NP-complete. Push the algorithm down to polynomial time and graph isomorphism joins sorting and primality, and the question closes. Prove it NP-complete instead and the polynomial hierarchy collapses, which would force a serious rethink of the foundations the field has been building on since the 1970s. Most people expect the first outcome, or at least expect the second to be impossible, and neither has happened.

So the practical answer is boring and the theoretical answer is missing. The demo above is a fair picture of why: checking a mapping costs 28 comparisons and always will, while nobody can yet say what finding one costs in general.