Graph isomorphism problem
Can it be decided in polynomial time whether two graphs are the same up to relabelling?
Summary
Why it is open
An isomorphism between two graphs is a one-to-one map between their vertices that preserves adjacency; the graph isomorphism problem (GI) asks whether one exists [7]. A proposed isomorphism is easy to check, so GI is in NP [7]. It is also universal for a broad family of problems: deciding isomorphism of any explicitly given finite structure reduces to GI in polynomial time [7].
A resolution would be a polynomial-time algorithm, or a proof that none exists. Because GI is in NP, the second would also prove P ≠ NP (see the Papex page P versus NP). The fastest known algorithm, László Babai's, runs in quasipolynomial time, exp((log n)^O(1)) for graphs with n vertices [4, 11], and Babai has written that "it is quite possible that the intermediate status of GI (neither NP-complete, nor polynomial time) will persist" [4].
Nor is GI expected to be NP-complete, that is, among the hardest problems in NP [7]. It lies in the class coAM, roughly meaning that non-isomorphism has short interactive proofs checked by a randomised verifier, so if GI were NP-complete the polynomial hierarchy, a tower of complexity classes built on NP, would collapse to its second level; Babai attributes this to Oded Goldreich, Silvio Micali and Avi Wigderson [4], and Brendan McKay and Adolfo Piperno note that NP-completeness "is considered unlikely" for this reason [3]. Babai's algorithm adds that GI is not NP-complete unless all of NP can be solved in quasipolynomial time [4]. Whether GI is in coNP is not known [4, 7]. The Wikipedia list on which this page's status rests asks whether GI "can be solved in polynomial time on a classical computer" [12].
What is known
Group theory and refinement (1979–1992). Group theory was first used for GI in 1979, to test isomorphism of graphs whose vertices carry colours, each colour used a bounded number of times [4, 7]. Eugene Luks showed in 1980 that graphs of bounded degree can be tested in polynomial time [1, 7]. Combined with a partitioning lemma of V. N. Zemlyachenko, his method gave the bound exp(O(√(n log n))) in 1983, the best known for three decades [4]. The "naive refinement" algorithm, which repeatedly splits vertices by the colours of their neighbours, decides isomorphism for almost all graphs in linear time [7]. Jin-Yi Cai, Martin Fürer and Neil Immerman showed in 1992 that combinatorial refinement alone cannot succeed in less than exponential time [2, 7]. Their hard pairs are coloured graphs with bounded colour classes, which the 1979 group-theoretic method already handles in polynomial time [4].
Babai's algorithm (2015–2016). Babai announced a quasipolynomial-time algorithm in November 2015 and posted the full paper on arXiv in December 2015, with a second version in January 2016; an extended abstract appeared at STOC 2016 [4, 5]. Its main theorem says that string isomorphism under a permutation group, and hence GI and the coset intersection problem, can be solved in quasipolynomial time [4]. The algorithm follows Luks's framework, which meets a barrier at large primitive groups, the "Johnson groups"; Babai attacks these with group-theoretic "local certificates" and combinatorial partitioning, and shows that Johnson graphs are the only obstructions to effective canonical partitioning [4]. A key lemma relies on the classification of finite simple groups [7]; Harald Helfgott reports a variant by L. Pyber that removes this dependence [8]. Babai stresses that the result concerns worst-case complexity and has "little relevance to practical computation" [7].
The 2017 error and its fix. On 1 January 2017 Helfgott, preparing an exposition for the Bourbaki seminar, pointed out an error in the timing analysis of the "Split-or-Johnson" routine [5, 8]. On 4 January Babai withdrew the quasipolynomial claim: the revised analysis gave exp(exp(Õ(√(log n)))), still faster than exp(n^ε) for every ε > 0, but not quasipolynomial [5]. On 7 January he found a replacement for the recursive call that had caused the problem, and on 9 January he wrote: "With this modification, I claim that the Graph Isomorphism test runs in quasipolynomial time (now really)" [5]. A note of 14 January describes the fix; it also reports a less serious error in the "Design Lemma" algorithm, pointed out by Jin-Yi Cai in spring 2016, whose corrected analysis Babai says "was additionally verified by Gábor Tardos and by Harald Helfgott" [5]. In the English translation of his Bourbaki exposition, Helfgott writes: "The preparation of this article led me to find a non-trivial error in the time analysis, but Babai was able to repair it by simplifying the algorithm. The proof is now correct" [8]. On 14 October 2026 the arXiv paper was still at its January 2016 version, and Babai's home page, next to the update notice, said: "This paper has not been fully peer-reviewed" [4, 5]. In a 2019 preliminary report Babai outlined how to turn the test, within the same time bound, into a canonical form [9]: a relabelling that makes isomorphic graphs identical [3].
Group isomorphism (2013–2026). Deciding whether two groups given by their multiplication (Cayley) tables are isomorphic reduces to GI [4, 11]. A simple algorithm attributed to Tarjan runs in time n^(log n + O(1)) for groups of order n, and the best bound for general groups is n^((1/4 + o(1)) log n) [10, 11]. Babai called group isomorphism "a barrier to placing GI in P" [4], and Joshua Grochow, Gábor Ivanyos, Youming Qiao and Xiaorui Sun describe it as "a significant bottleneck to further progress on GI" [11]. Isomorphism of p-groups of class 2 and exponent p had been identified as "a major barrier" to faster group isomorphism; in 2023 Sun gave an n^O((log n)^(5/6)) algorithm for them for every prime p > 2 [10], and later work extended n^o(log n) bounds to other p-groups of class 2 with p odd [11]. An October 2026 preprint by Grochow, Ivanyos, Qiao and Sun, accepted to FOCS 2026 according to its arXiv listing, gives an N^O((log N)^(1/2)) algorithm for 2-groups of Frattini class 2, in the case p = 2, where there had been "essentially no progress until now" [11].
Status. No polynomial-time algorithm is known, "despite many published claims", as McKay and Piperno put it [3]. On 14 October 2026 the Wikipedia list still included the problem [12].
Main approaches
Group-theoretic divide and conquer. Reduce GI to string isomorphism and recurse on the structure of the permutation group, as Luks and Babai did [1, 4]. Strongest evidence: the quasipolynomial algorithm [4, 8]. Main difficulty: the group isomorphism barrier described above [4, 11].
Combinatorial refinement. Distinguish vertices by refining colourings, from naive vertex refinement to the Weisfeiler–Leman method on pairs and tuples of vertices [4, 7]. Strongest evidence: naive refinement decides almost all graphs in linear time [7]. Main difficulty: by Cai, Fürer and Immerman, refinement alone needs exponential time on some pairs of graphs [2, 7].
Practical solvers. Programs such as nauty and Traces fix vertices one at a time, refine the resulting partitions and use automorphisms to prune the search tree [3]. Strongest evidence: McKay and Piperno found Traces the leader on most of the difficult graph classes they tested, and nauty preferred for mass testing of small graphs [3]. Main difficulty: Daniel Neuen and Pascal Schweitzer built a family of graphs on which algorithms following this individualization-refinement paradigm need exponential time, whatever cell selector or heuristic invariants they use [6].
Attacking group isomorphism. Translate isomorphism of nilpotent groups into problems about spaces of matrices and solve those [10, 11]. Strongest evidence: n^o(log n) algorithms for p-groups of class 2 with p odd, and now for 2-groups of Frattini class 2 [10, 11]. Main difficulty: the methods so far cover groups of nilpotency class 2, and the bound for general groups is still n^((1/4 + o(1)) log n) [10, 11].
Open sub-questions
- Group isomorphism. Can isomorphism of groups given by Cayley tables be decided in n^o(log n) time for all groups, not only for p-groups of class 2 [4, 10, 11]?
- coNP. Is GI in coNP? Babai notes that group isomorphism is not known to be in coNP either [4].
- Space. Can GI be solved in quasipolynomial time and polynomial space, a question Babai attributes to Luks [7]?
- Canonical forms. Babai's 2019 preliminary report outlines quasipolynomial-time canonical forms [9]; is graph canonization polynomial-time equivalent to GI, as the Wikipedia list asks [12]?
- Hypergraphs. Can isomorphism of hypergraphs be decided in time quasipolynomial in the number of vertices and polynomial in the number of edges [7]?
- Hardness for P. Is there a logspace reduction from the circuit value problem to GI? Babai notes that this would be strong evidence against an efficient parallel algorithm [7].
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Luks, E. M. (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time. Journal of Computer and System Sciences 25(1), 42–65. 10.1016/0022-0000(82)90009-5 · Checked 14 Oct 2026
- Cai, J.-Y., Fürer, M. & Immerman, N. (1992). An optimal lower bound on the number of variables for graph identification. Combinatorica 12(4), 389–410. 10.1007/BF01305232 · Checked 14 Oct 2026
- McKay, B. D. & Piperno, A. (2014). Practical graph isomorphism, II. Journal of Symbolic Computation 60, 94–112. 10.1016/j.jsc.2013.09.003 · Checked 14 Oct 2026
- Babai, L. (2016). Graph isomorphism in quasipolynomial time (extended abstract). In Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (STOC '16), 684–697. Full version: arXiv preprint 1512.03547, version 2 of 19 January 2016. 10.1145/2897518.2897542 · Checked 14 Oct 2026
- Babai, L. (2017). Graph Isomorphism update, January 9, 2017 (with the January 4 posting appended), and Fixing the UPCC case of Split-or-Johnson (note dated 14 January 2017). Source · Checked 14 Oct 2026
- Neuen, D. & Schweitzer, P. (2018). An exponential lower bound for individualization-refinement algorithms for graph isomorphism. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC '18), 138–150. 10.1145/3188745.3188900 · Checked 14 Oct 2026
- Babai, L. (2019). Groups, graphs, algorithms: the graph isomorphism problem. In Proceedings of the International Congress of Mathematicians (ICM 2018), Rio de Janeiro, 3319–3336. 10.1142/9789813272880_0183 · Checked 14 Oct 2026
- Helfgott, H. A. (2019). Isomorphismes de graphes en temps quasi-polynomial (d'après Babai et Luks, Weisfeiler–Leman, ...). Astérisque 407 (Séminaire Bourbaki, exposé 1125), 135–182. 10.24033/ast.1063 · Checked 14 Oct 2026
- Babai, L. (2019). Canonical form for graphs in quasipolynomial time: preliminary report. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (STOC '19), 1237–1246. 10.1145/3313276.3316356 · Checked 14 Oct 2026
- Sun, X. (2023). Faster isomorphism for p-groups of class 2 and exponent p. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC '23), 433–440. 10.1145/3564246.3585250 · Checked 14 Oct 2026
- Grochow, J. A., Ivanyos, G., Qiao, Y. & Sun, X. (2026). Beyond odd characteristic: faster isomorphism testing of 2-groups of Frattini class 2. arXiv preprint 2610.00874 (version 1, 1 October 2026; comment: accepted to FOCS 2026), not peer reviewed in this version. Source · Checked 14 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 14 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 29 Sep 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.