Graph isomorphism complexity

A graph records dots and which pairs are connected. Two drawings can describe the same graph even when the dots have different names or positions. For example, the four connections AB, BC, CD and DA make a loop; renaming A, B, C and D as w, y, x and z gives the connections wy, yx, xz and zw. Graph isomorphism asks whether such a renaming makes every connection match. Can one method decide this for every pair of finite graphs, with its number of steps bounded by one fixed power of the input size? A bound based on input size squared, for example, allows four times as much work when the input doubles; the power must stay fixed as graphs grow.[3]

A graph consists of dots, called vertices, and connections between pairs of dots. Two graphs are isomorphic when a one-to-one renaming of their vertices preserves every connection. Can this be decided for arbitrary finite graphs in polynomial worst-case time? For graphs with $n$ vertices, a direct search tests $n!$ renamings, where $n!$ multiplies the integers from one to $n$. Structural tests can rule out many candidates without trying them all. A vertex’s degree is its number of neighbours, so matching vertices must have equal degrees. But degree alone is insufficient: a loop on six vertices and two separate triangles both give every vertex degree two, yet one has a single connected piece and the other has two.

For graphs $G,H$, the required bijection $\phi$ satisfies $\{u,v\}\in E(G)$ if and only if $\{\phi(u),\phi(v)\}\in E(H)$, where $E$ denotes the edge set. The target is a running time bounded by $C L^a$, with $L$ the encoded input length and constants $C,a$ independent of the inputs. Babai’s quasipolynomial milestone gives a bound of the form $\exp((\log n)^{O(1)})$, where $O(1)$ means that the power is bounded by a constant independent of $n$. This allows the effective power of $n$ to grow with $n$; it does not supply the desired fixed-power guarantee.[1] [3]

Checking a proposed renaming is easy: check each pair of dots. Finding a match, or ruling out every possible match, can be harder. The missing guarantee must cover the most demanding input pairs as the graphs grow; quick answers on familiar networks do not provide it.[3]

The August 2026 preprint treats tournaments: directed graphs with exactly one arrow between each pair of vertices. Its bounded VC dimension assumption limits the richness of which vertex subsets can appear as outgoing-neighbour patterns. For a fixed bound it obtains polynomial time, but this family restriction leaves arbitrary graphs outside the guarantee. Babai’s older arXiv version predates a correction to its time analysis; Helfgott’s 2017 exposition describes the repaired quasipolynomial result.[2] [3]

Names and drawing positions can hide that two stored networks have exactly the same structure. Recognizing them prevents one structure from being counted repeatedly as different objects. It is also a basic test of what computers can discover about a structure without depending on arbitrary labels.[3]

Many possible matches arise from symmetries, meaning renamings that leave a graph unchanged. A symmetry can create many equivalent choices, but describing them together can also save work. The known algorithm exploits this tension through structural partitions and groups of permutations. A polynomial-time result would show that the ambiguity caused by labels and symmetry can always be organized without an ever-growing power of the input size.[3]