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)
“The problem is simply this: no one can feel like CEO of his or her life in the presence of the people who toilet trained her and spanked him when he was naughty. We may have become Masters of the Universe, accustomed to giving life and taking it away, casually ordering people into battle or out of their jobs . . . and yet we may still dirty our diapers at the sound of our mommy’s whimper or our daddy’s growl.”
—Frank Pittman (20th century)