Can graph isomorphism be solved in polynomial time?
Given two graphs on vertices, decide whether they are isomorphic, that is, whether some relabeling of the vertices of one turns it into the other. Is there an algorithm that does this in time polynomial in ?
History and references
Still open as of 2026.
Graph isomorphism is in NP but is not known to be either in P or NP-complete, which makes it one of the few natural candidates for an intermediate problem. It lies in the low hierarchy of NP, so it cannot be NP-complete unless the polynomial hierarchy collapses to its second level. Polynomial algorithms are known for many special classes, including trees, planar graphs and graphs of bounded treewidth. In 2015 László Babai announced an algorithm running in quasipolynomial time . Harald Helfgott found an error in January 2017, Babai repaired it within days, and Helfgott confirmed the fix, although as of 2025 the full version had not appeared in a journal. Whether the quasipolynomial bound can be brought down to polynomial is open.
References
Solutions 0
Sign in or create an account to publish a solution