[1] The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate.
It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group.
[8][9][10][11] On January 4, 2017, Babai retracted the quasi-polynomial claim and stated a sub-exponential time bound instead after Harald Helfgott discovered a flaw in the proof.
The algorithm has run time 2O(√n log n) for graphs with n vertices and relies on the classification of finite simple groups.
There are several competing practical algorithms for graph isomorphism, such as those due to McKay (1981), Schmidt & Druffel (1976), Ullman (1976), and Stoichev (2019).
For the latter two problems, Babai, Kantor & Luks (1983) obtained complexity bounds similar to that for graph isomorphism.
[34] That it lies in Parity P means that the graph isomorphism problem is no harder than determining whether a polynomial-time nondeterministic Turing machine has an even or odd number of accepting paths.
[35] This essentially means that an efficient Las Vegas algorithm with access to an NP oracle can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time.
Manuel Blum and Sampath Kannan (1995) have shown a probabilistic checker for programs for graph isomorphism.
Suppose P is a claimed polynomial-time procedure that checks if two graphs are isomorphic, but it is not trusted.
Chemical database search is an example of graphical data mining, where the graph canonization approach is often used.
[49] In particular, a number of identifiers for chemical substances, such as SMILES and InChI, designed to provide a standard and human-readable way to encode molecular information and to facilitate the search for such information in databases and on the web, use canonization step in their computation, which is essentially the canonization of the graph which represents the molecule.