Editing Graph isomorphism (section)

==Recognition of graph isomorphism==
{{main article|Graph isomorphism problem}}

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. The computational problem of determining whether two finite graphs are isomorphic is called the graph isomorphism problem.

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]]).

The graph isomorphism problem  is one of few standard problems in [[computational complexity theory]] belonging to [[NP (complexity)|NP]], but not known to belong to either of its well-known (and, if [[P versus NP problem|P&nbsp;≠&nbsp;NP]], disjoint) subsets: [[P (complexity)|P]] and [[NP-complete]]. It is one of only two, out of 12 total, problems listed in {{harvtxt|Garey|Johnson|1979}} whose complexity remains unresolved, the other being [[integer factorization]].  It is however known that if the problem is NP-complete then the [[polynomial hierarchy]] collapses to a finite level.<ref>{{cite journal | title=Graph isomorphism is in the low hierarchy | first=Uwe | last=Schöning | journal=[[Journal of Computer and System Sciences]] | volume=37 | issue=3 | year=1988 | pages=312–323 | doi=10.1016/0022-0000(88)90010-4| doi-access= }}</ref>

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]].<ref>{{citation|doi=10.1126/science.aad7416|journal=[[Science (journal)|Science]]|first=Adrian|last=Cho|date=November 10, 2015|title=Mathematician claims breakthrough in complexity theory}}.</ref><ref>{{citation|last=Klarreich|first=Erica|url=https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/|title=Landmark Algorithm Breaks 30-Year Impasse|journal=[[Quanta Magazine]]|date=December 14, 2015}}</ref> He published preliminary versions of these results in the proceedings of the 2016 [[Symposium on Theory of Computing]],<ref>{{citation|last=Babai|first=László|contribution=Graph isomorphism in quasipolynomial time [extended abstract]|doi=10.1145/2897518.2897542|mr=3536606|pages=684–697|publisher=ACM, New York|title=STOC'16—Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing|year=2016|isbn=978-1-4503-4132-5 |s2cid=17118954 }}</ref> and of the 2018 [[International Congress of Mathematicians]].<ref>{{citation|last=Babai|first=László|contribution=Group, graphs, algorithms: the graph isomorphism problem|mr=3966534|pages=3319–3336|publisher=World Sci. Publ., Hackensack, NJ|title=Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. IV. Invited lectures|year=2018}}</ref> In January 2017, Babai briefly retracted the quasi-polynomiality claim and stated a [[sub-exponential time]] complexity bound instead. He restored the original claim five days later.<ref>{{citation|last=Babai|first= László|url=http://people.cs.uchicago.edu/~laci/update.html|title=Graph isomorphism update|date=January 9, 2017}}</ref> {{as of|2024}}, the full journal version of Babai's paper has not yet been published.

Its generalization, the [[subgraph isomorphism problem]], is known to be NP-complete.

The main areas of research for the problem are design of fast algorithms  and theoretical investigations of its [[Analysis of algorithms|computational complexity]], both for the general problem and for special classes of graphs.

The [[Weisfeiler Leman graph isomorphism test]] can be used to heuristically test for graph isomorphism.<ref>{{cite book|arxiv=2201.07083 |doi=10.1109/ICASSP39728.2021.9413523 |chapter=A Short Tutorial on the Weisfeiler-Lehman Test and Its Variants |title=ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) |date=2021 |last1=Huang |first1=Ningyuan Teresa |last2=Villar |first2=Soledad |pages=8533–8537 |isbn=978-1-7281-7605-5 |s2cid=235780517 }}</ref> If the test fails the two input graphs are guaranteed to be non-isomorphic. If the test succeeds the graphs may or may not be isomorphic. There are generalizations of the test algorithm that are guaranteed to detect isomorphisms, however their run time is exponential.

Another well-known algorithm for graph isomorphism is the vf2 algorithm, developed by Cordella et al. in 2001.<ref>{{cite journal|last1=Cordella|first1=L. P.|last2=Foggia|first2=P.|last3=Sansone|first3=C.|last4=Vento|first4=M.|title=An Improved Algorithm for Matching Large Graphs|journal=3rd IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition|pages=149–159|year=2001|url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=f3e10bd7521ec6263a58fdaa4369dfe8ad50888c}}</ref> The vf2 algorithm is a depth-first search algorithm that tries to build an isomorphism between two graphs incrementally. 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.