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.

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

This problem is a special case of the subgraph isomorphism problem,[3] which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H and 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.[4]

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

State of the art

The best currently accepted theoretical algorithm is due to Babai & Luks (1983), and is based on the earlier work by Luks (1982) combined with a subfactorial algorithm of V. N. Zemlyachenko (Zemlyachenko, Korneenko & Tyshkevich 1985). The algorithm has run time 2O(n log n) for graphs with n vertices and relies on the classification of finite simple groups. Without CFSG, a slightly weaker bound 2O(n log2 n) was obtained first for strongly regular graphs by László Babai (1980), and then extended to general graphs by Babai & Luks (1983). Improvement of the exponent n is a major open problem; for strongly regular graphs this was done by Spielman (1996). For hypergraphs of bounded rank, a subexponential upper bound matching the case of graphs was obtained by Babai & Codenotti (2008).

In November 2015, Babai announced a quasipolynomial time algorithm for all graphs, that is, one with running time for some fixed .[6][7][8] 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.[9][10]

There are several competing practical algorithms for graph isomorphism, such as those due to McKay (1981), Schmidt & Druffel (1976), and Ullman (1976). While they seem to perform well on random graphs, a major drawback of these algorithms is their exponential time performance in the worst case.[11]

The graph isomorphism problem is computationally equivalent to the problem of computing the automorphism group of a graph, and is weaker than the permutation group isomorphism problem and the permutation group intersection problem. For the latter two problems, Babai, Kantor & Luks (1983) obtained complexity bounds similar to that for graph isomorphism.

Solved special cases

A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:

Complexity class GI

Since the graph isomorphism problem is neither known to be NP-complete nor known to be tractable, researchers have sought to gain insight into the problem by defining a new class GI, the set of problems with a polynomial-time Turing reduction to the graph isomorphism problem.[25] If in fact the graph isomorphism problem is solvable in polynomial time, GI would equal P.

As is common for complexity classes within the polynomial time hierarchy, a problem is called GI-hard if there is a polynomial-time Turing reduction from any problem in GI to that problem, i.e., a polynomial-time solution to a GI-hard problem would yield a polynomial-time solution to the graph isomorphism problem (and so all problems in GI). A problem is called complete for GI, or GI-complete, if it is both GI-hard and a polynomial-time solution to the GI problem would yield a polynomial-time solution to .

The graph isomorphism problem is contained in both NP and co-AM. GI is contained in and low for Parity P, as well as contained in the potentially much smaller class SPP.[26] That it lies in Parity P means that the graph isomorphism problem is no harder than determining whether a polynomial-time nondeterministic Turing machine has an even or odd number of accepting paths. GI is also contained in and low for ZPPNP.[27] This essentially means that an efficient Las Vegas algorithm with access to an NP oracle can solve graph isomorphism so easily that it gains no power from being given the ability to do so in constant time.

GI-complete and GI-hard problems

Isomorphism of other objects

There are a number of classes of mathematical objects for which the problem of isomorphism is a GI-complete problem. A number of them are graphs endowed with additional properties or restrictions:[28]

GI-complete classes of graphs

A class of graphs is called GI-complete if recognition of isomorphism for graphs from this subclass is a GI-complete problem. The following classes are GI-complete:[28]

Many classes of digraphs are also GI-complete.

Other GI-complete problems

There are other nontrivial GI-complete problems in addition to isomorphism problems.

GI-hard problems

Program checking

Manuel Blum and Sampath Kannan (1995) have shown a probabilistic checker for programs for graph isomorphism. Suppose P is a claimed polynomial-time procedure that checks if two graphs are isomorphic, but it is not trusted. To check if G and H are isomorphic:

This procedure is polynomial-time and gives the correct answer if P is a correct program for graph isomorphism. If P is not a correct program, but answers correctly on G and H, the checker will either give the correct answer, or detect invalid behaviour of P. If P is not a correct program, and answers incorrectly on G and H, the checker will detect invalid behaviour of P with high probability, or answer wrong with probability 2−100.

Notably, P is used only as a blackbox.

Applications

Graphs are commonly used to encode structural information in many fields, including computer vision and pattern recognition, and graph matching, i.e., identification of similarities between graphs, is an important tools in these areas. In these areas graph isomorphism problem is known as the exact graph matching. [38]

In cheminformatics and in mathematical chemistry, graph isomorphism testing is used to identify a chemical compound within a chemical database.[39] Also, in organic mathematical chemistry graph isomorphism testing is useful for generation of molecular graphs and for computer synthesis.

Chemical database search is an example of graphical data mining, where the graph canonization approach is often used.[40] In particular, a number of identifiers for chemical substances, such as SMILES and InChI, designed to provide a standard and human-readable way to encode molecular information and to facilitate the search for such information in databases and on the web, use canonization step in their computation, which is essentially the canonization of the graph which represents the molecule.

In electronic design automation graph isomorphism is the basis of the Layout Versus Schematic (LVS) circuit design step, which is a verification whether the electric circuits represented by a circuit schematic and an integrated circuit layout are the same.[41]

See also

Notes

  1. Schöning (1987).
  2. McKay (1981).
  3. Ullman (1976).
  4. Moore, Russell & Schulman (2008).
  5. Endika Bengoetxea, "Inexact Graph Matching Using Estimation of Distribution Algorithms", Ph. D., 2002, Chapter 2:The graph matching problem (retrieved June 28, 2017)
  6. "Mathematician claims breakthrough in complexity theory". Science. Nov 10, 2015.
  7. Babai (2015)
  8. Video of first 2015 lecture linked from Babai's home page
  9. Babai, László (January 9, 2017), Graph isomorphism update
  10. Erika Klarreich, Graph Isomorphism Vanquished — Again, Quanta Magazine, January 14, 2017 see here
  11. Foggia, Sansone & Vento (2001).
  12. Kelly (1957).
  13. Aho, Hopcroft & Ullman (1974), p. 84-86.
  14. Hopcroft & Wong (1974).
  15. Datta et al. (2009).
  16. Booth & Lueker (1979).
  17. Colbourn (1981).
  18. Muzychuk (2004).
  19. Bodlaender (1990).
  20. Miller 1980; Filotti & Mayer 1980.
  21. Luks (1982).
  22. Babai, Grigoryev & Mount (1982).
  23. Miller (1983).
  24. Luks (1986).
  25. Booth & Colbourn 1977; Köbler, Schöning & Torán 1993.
  26. Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
  27. Arvind & Köbler (2000).
  28. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 Zemlyachenko, Korneenko & Tyshkevich (1985)
  29. Narayanamurthy & Ravindran (2008).
  30. Grigor'ev (1981).
  31. Johnson (2005); Kaibel & Schwartz (2003).
  32. Chung (1985).
  33. 1 2 Kaibel & Schwartz (2003).
  34. Colbourn & Colbourn (1978).
  35. Kozen (1978).
  36. Shawe-Taylor & Pisanski (1994).
  37. Mathon (1979); Johnson 2005.
  38. Endika Bengoetxea, Ph.D., Abstract
  39. Irniger (2005).
  40. Cook & Holder (2007).
  41. Baird & Cho (1975).

References

Surveys and monographs

Software

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.