Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Graph isomorphism problem
Summary
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
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 known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.
This problem is a special case of the subgraph isomorphism problem, which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H; this problem is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group.
In the area of it is known as the exact graph matching.
In November 2015, László Babai announced a quasipolynomial time algorithm for all graphs, that is, one with running time for some fixed . 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. On January 9, 2017, Babai announced a correction (published in full on January 19) and restored the quasi-polynomial claim, with Helfgott confirming the fix. Helfgott further claims that one can take c = 3, so the running time is 2O((log n)3).
Prior to this, the best accepted theoretical algorithm was due to , and was based on the earlier work by combined with a subfactorial algorithm of V. N. Zemlyachenko . The algorithm has run time 2O() for graphs with n vertices and relies on the classification of finite simple groups. Without this classification theorem, a slightly weaker bound
2O( log2 n) was obtained first for strongly regular graphs by , and then extended to general graphs by . Improvement of the exponent for strongly regular graphs was done by .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.