The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
Besides its practical importance, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete: it is one of only 12 such problems listed by Garey & Johnson (1979), and one of only two of that list whose complexity remains unresolved (the other being integer factorization). As of 2008 the best algorithm (Luks, 1983) has run time 2O(√(n log n)) for graphs with n vertices.
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 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.
Read more about Graph Isomorphism Problem: State of The Art, Solved Special Cases, Complexity Class GI, Program Checking, Applications
Famous quotes containing the words graph and/or problem:
“When producers want to know what the public wants, they graph it as curves. When they want to tell the public what to get, they say it in curves.”
—Marshall McLuhan (1911–1980)
“A curious thing about the ontological problem is its simplicity. It can be put in three Anglo-Saxon monosyllables: ‘What is there?’ It can be answered, moveover, in a word—‘Everything.’”
—Willard Van Orman Quine (b. 1908)