Papex

Open problem · Computer science · Open

Graph isomorphism problem

Can it be decided in polynomial time whether two graphs are the same up to relabelling?

Summary

Deciding whether two finite graphs are isomorphic is not known to be solvable in polynomial time, nor to be NP-complete.

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

  1. 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]?
  2. coNP. Is GI in coNP? Babai notes that group isomorphism is not known to be in coNP either [4].
  3. Space. Can GI be solved in quasipolynomial time and polynomial space, a question Babai attributes to Luks [7]?
  4. 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]?
  5. Hypergraphs. Can isomorphism of hypergraphs be decided in time quasipolynomial in the number of vertices and polynomial in the number of edges [7]?
  6. 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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 14 Oct 2026

Page reviewed 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.

More in Computing