Graph isomorphism problem

Unsolved problem in computer science:
Can the graph isomorphism problem be solved in polynomial time?
(more unsolved problems in computer science)

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.[1]

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.[2] 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.[3][4]

This problem is a special case of the subgraph isomorphism problem,[5] 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.[6]

In the area of image recognition it is known as the exact graph matching.[7]

  1. ^ Kobler, Johannes; Schöning, Uwe; Torán, Jacobo (2012). The graph isomorphism problem: its structural complexity. Springer Science & Business Media. p. 1.
  2. ^ Schöning (1987).
  3. ^ Babai, László; Erdős, Paul; Selkow, Stanley M. (1980-08-01). "Random Graph Isomorphism". SIAM Journal on Computing. 9 (3): 628–635. doi:10.1137/0209047. ISSN 0097-5397.
  4. ^ McKay (1981).
  5. ^ Ullman (1976).
  6. ^ Moore, Russell & Schulman (2008).
  7. ^ Endika Bengoetxea, "Inexact Graph Matching Using Estimation of Distribution Algorithms", Ph. D., 2002, Chapter 2:The graph matching problem (retrieved June 28, 2017)