Papex

Open problem · Computer science · Open

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.

More in Computing