Deterministic $n^{O(\log n)}$ Graph Isomorphism Algorithm via Inherited Decompositions
MohammadTaghi Hajiaghayi, Mahdi JafariRaviz
cs.DS
Nov 1, 2026 · v1
TL;DR
Lean files formalizing the main theorem, the deterministic n^{O(log n)} graph isomorphism bound, are released in a GitHub repository.
Abstract
We give a deterministic $n^{O(\log n)}$-time algorithm for graph isomorphism. To our knowledge, this is the first proof of such a worst-case bound for general graphs. The algorithm uses the local-certificate and color-refinement steps of Babai's quasipolynomial algorithm, but retains the decomposition of each recursive instance when it solves an auxiliary coloring problem. There are two reasons for retaining this information. First, a local test can make progress without removing many vertices: it can eliminate a layer of permutation symmetry. A logarithmic bound on the total weight of these layers allows tests of constant size. Second, the auxiliary bipartite graphs arising in the symmetry-breaking step can be represented inside the current instance, after retaining a row decomposition when necessary. These recursive calls inherit the progress already made. The analysis gives a recurrence with quadratic logarithmic cost and a fixed power decrease in every fresh recursive call, improving the explicit cubic logarithmic exponent in the analysis of the corrected Luks–Babai algorithm. We present the algorithm through colorings, partitions, and bipartite graphs, and collect the permutation-group ingredients in one appendix. The result extends to string isomorphism and returns one isomorphism and generators for the full automorphism group.
Problem
Graph isomorphism has a quasipolynomial algorithm (Babai), but the best explicit bound for the corrected Luks–Babai algorithm is exp(O((log n)^3)). The goal is a deterministic n^{O(log n)} worst-case bound for general graphs.
Approach
The algorithm reuses the local-certificate and color-refinement steps of Babai's algorithm. It keeps the partition hierarchy of each recursive instance, with caps on alternating sections, so later auxiliary problems inherit progress already made. Local tests of constant size can eliminate a layer of permutation symmetry, and the symmetry-breaking step stops at its first auxiliary bipartite graph, which is represented inside the current instance. A potential combining domain size, hierarchy rank, symmetry measure and width bounds yields a recurrence with quadratic-logarithmic cost per phase.
Results
A deterministic exp(O((log n)^2)) = n^{O(log n)} algorithm for graph isomorphism, which also extends to string isomorphism and returns generators of the full automorphism group. Lean files formalizing the main theorem are provided on GitHub.