Graph canonisation versus graph isomorphism
Is computing a canonical form of a graph no harder, up to polynomial time, than deciding whether two graphs are isomorphic?
Summary
Graph canonisation gives every graph a standard labelled form shared by all graphs isomorphic to it, so it is at least as hard as graph isomorphism. Whether the two problems are polynomial-time equivalent is open; in 2019 László Babai announced a quasi-polynomial-time algorithm for canonisation.
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 18 Nov 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.