Open problem, Applied and computational mathematics, Combinatorics and discrete mathematics, posed 1971

Complexity of graph isomorphism

Open

Given two finite simple graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ on $n = |V_1| = |V_2|$ vertices, the Graph Isomorphism ( $\mathrm{GI}$ ) problem asks whether there exists a bijection $\varphi : V_1 \to V_2$ such that $\{u, v\} \in E_1$ if and only if $\{\varphi(u), \varphi(v)\} \in E_2$ . Does $\mathrm{GI}$ belong to the complexity class $\mathsf{P}$ (deterministic polynomial time $n^{O(1)}$ )?

Posed by, 1971Stephen Cook

Research frontier as of 2026

As of 2026, whether Graph Isomorphism belongs to $\mathsf{P}$ remains open. László Babai's 2015–2017 quasipolynomial-time algorithm establishes the upper bound $\exp((\log n)^{O(1)})$ (and Harald Helfgott showed the exponent in $(\log n)^c$ can be taken with $c = 3$ ). Following Babai's breakthrough, polylogarithmic-dimension Weisfeiler–Leman ( $(\log n)^{O(1)}$ - $\mathrm{WL}$ ) and dynamic programming extensions have been developed, while Jin-Yi Cai, Fürer, and Immerman (1992) proved that no fixed-dimension $k$ - $\mathrm{WL}$ test can solve $\mathrm{GI}$ on all graphs.

Best known results

Babai (2015–2017): Graph Isomorphism, String Isomorphism, and Coset Intersection are solvable in deterministic quasipolynomial time $\exp((\log n)^{O(1)})$ .
Luks (1982) and Grohe–Neuen–Schweitzer (2018): for graphs of maximum degree $d$ , isomorphism can be tested in time $n^{\operatorname{poly}(\log d)}$ .
Schöning (1988): $\mathrm{GI}$ is in the low hierarchy $\mathsf{Low}_2$ , and cannot be $\mathsf{NP}$ -complete unless the polynomial hierarchy collapses to $\mathsf{\Sigma}_2^{\mathsf{P}} = \mathsf{\Pi}_2^{\mathsf{P}}$ .

Tools and where they stop

Tool	Achieved	Where it stops
Luks's permutation group divide-and-conquer and Babai's local certificates / Design Lemma	Reduces giant permutation group actions $S_k$ or $A_k$ on Johnson graphs via canonical $2$ -step partitioning in $O(\log n)$ recursion depth	Multiplicative branching factors across $O(\log n)$ levels of recursion accumulate to $n^{\operatorname{polylog}(n)}$ rather than $n^{O(1)}$
Weisfeiler–Leman ( $k$ - $\mathrm{WL}$ ) color refinement	Solves isomorphism in polynomial time on almost all random graphs and on graphs excluding a fixed minor	Cai–Fürer–Immerman (1992) gadget graphs force $k = \Omega(n)$ for purely combinatorial $k$ - $\mathrm{WL}$ without group-theoretic coset management

Open questions

Does Graph Isomorphism belong to $\mathsf{P}$ , i.e., can it be solved in deterministic time $n^{O(1)}$ ?
Can the exponent $c$ in the quasipolynomial running time $\exp(O((\log n)^c))$ for Graph Isomorphism be reduced below $3$ , or to $1 + o(1)$ ?

References

László Babai (2016). Graph isomorphism in quasipolynomial time · DOI:10.1145/2897518.2897542 · arXiv:1512.03547
Eugene M. Luks (1982). Isomorphism of graphs of bounded valence can be tested in polynomial time · DOI:10.1016/0022-0000(82)90009-5
Uwe Schöning (1988). Graph isomorphism is in the low hierarchy · DOI:10.1016/0022-0000(88)90010-4