Graph isomorphism

The isomorphism relation may also be defined for all these generalizations of graphs: the isomorphism bijection must preserve the elements of structure which define the object type in question: arcs, labels, vertex/edge colors, the root of the rooted tree, etc.

[7] While graph isomorphism may be studied in a classical mathematical way, as exemplified by the Whitney theorem, it is recognized that it is a problem to be tackled with an algorithmic approach.

Its practical applications include primarily cheminformatics, mathematical chemistry (identification of chemical compounds), and electronic design automation (verification of equivalence of various representations of the design of an electronic circuit).

It is one of only two, out of 12 total, problems listed in Garey & Johnson (1979) whose complexity remains unresolved, the other being integer factorization.

[8] In November 2015, László Babai, a mathematician and computer scientist at the University of Chicago, claimed to have proven that the graph isomorphism problem is solvable in quasi-polynomial time.

[9][10] He published preliminary versions of these results in the proceedings of the 2016 Symposium on Theory of Computing,[11] and of the 2018 International Congress of Mathematicians.

[12] In January 2017, Babai briefly retracted the quasi-polynomiality claim and stated a sub-exponential time complexity bound instead.

There are generalizations of the test algorithm that are guaranteed to detect isomorphisms, however their run time is exponential.

It uses a set of feasibility rules to prune the search space, allowing it to efficiently handle graphs with thousands of nodes.

The vf2 algorithm has been widely used in various applications, such as pattern recognition, computer vision, and bioinformatics.

While it has a worst-case exponential time complexity, it performs well in practice for many types of graphs.