Graph isomorphism problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
List of unsolved problems in computer science
Is the graph isomorphism problem in P, or NP-complete, or neither?

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).[1] As of 2008 the best algorithm (Luks, 1983) has run time 2O(√(n log n)) for graphs with n vertices.[2][3]

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

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.[5]

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

State of the art[edit]

The best current theoretical algorithm is due to Eugene Luks (1983), and is based on the earlier work by Luks (1981), Babai & Luks (1982), combined with a subfactorial algorithm due to Zemlyachenko (1982). The algorithm 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 (1982). 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 recently obtained by Babai & Codenotti (2008).

On a side note, 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 and Luks (1983) obtained complexity bounds similar to that for the graph isomorphism.[8]

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

Solved special cases[edit]

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

Complexity class GI[edit]

Since the graph isomorphism problem is neither known to be NP-complete nor 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.[21] 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 X 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 X.

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.[22] 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.[23] 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[edit]

Isomorphism of other objects[edit]

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:[24]

GI-complete classes of graphs[edit]

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:[24]

Many classes of digraphs are also GI-complete.

Other GI-complete problems[edit]

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

  • The recognition of self-complementarity of a graph or digraph.[28]
  • A clique problem for a class of so-called M-graphs. It is shown that finding an isomorphism for n-vertex graphs is equivalent to finding an n-clique in an M-graph of size n2. This fact is interesting because the problem of finding an (n − ε)-clique in a M-graph of size n2 is NP-complete for arbitrarily small positive ε.[29]
  • The problem of homeomorphism of 2-complexes.[30]

GI-hard problems[edit]

  • The problem of counting the number of isomorphisms between two graphs is polynomial-time equivalent to the problem of telling whether even one exists.[31]
  • The problem of deciding whether two convex polytopes given by either the V-description or H-description are projectively or affinely isomorphic. The latter means existence of a projective or affine map between the spaces that contain the two polytopes (not necessarily of the same dimension) which induces a bijection between the polytopes.[27]

Program checking[edit]

Blum and Kannan[32] have shown a program checker 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:

  • Ask P whether G and H are isomorphic.
    • If the answer is "yes':
      • Attempt to construct an isomorphism using P as subroutine. Mark a vertex u in G and v in H, and modify the graphs to make them distinctive (with a small local change). Ask P if the modified graphs are isomorphic. If no, change v to a different vertex. Continue searching.
      • Either the isomorphism will be found (and can be verified), or P will contradict itself.
    • If the answer is "no":
      • Perform the following 100 times. Choose randomly G or H, and randomly permute its vertices. Ask P if the graph is isomorphic to G and H. (As in AM protocol for graph nonisomorphism).
      • If any of the tests are failed, judge P as invalid program. Otherwise, answer "no".

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[edit]

In cheminformatics and in mathematical chemistry, graph isomorphism testing is used to identify a chemical compound within a chemical database.[33] 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.[34] 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.[35]

See also[edit]

Notes[edit]

  1. ^ The latest one resolved was minimum-weight triangulation, proved to be NP-complete in 2006. Mulzer, Wolfgang; Rote, Günter (2008), "Minimum-weight triangulation is NP-hard", Journal of the ACM 55 (2): 1, arXiv:cs.CG/0601002, doi:10.1145/1346330.1346336 .
  2. ^ a b Johnson 2005
  3. ^ Babai & Codenotti (2008).
  4. ^ Uwe Schöning, "Graph isomorphism is in the low hierarchy", Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312–323
  5. ^ McKay 1981
  6. ^ Ullman (1976).
  7. ^ Cristopher Moore; Alexander Russell; Schulman, Leonard J. (2005). "The Symmetric Group Defies Strong Fourier Sampling: Part I". arXiv:quant-ph/0501056v3 [quant-ph].
  8. ^ László Babai, William Kantor, Eugene Luks, Computational complexity and the classification of finite simple groups, Proc. 24th FOCS (1983), pp. 162-171.
  9. ^ P. Foggia, C.Sansone, M. Vento, A Performance Comparison of Five Algorithms for Graph Isomorphism, Proc. 3rd IAPR-TC15 Workshop Graph-Based Representations in Pattern Recognition, 2001, pp. 188-199.
  10. ^ P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957) pp. 961–968; Aho, Hopcroft & Ullman 1974.
  11. ^ Hopcroft & Wong 1974
  12. ^ Datta, S.; Limaye, N.; Nimbhorkar, P.; Thierauf, T.; Wagner, F. (2009). "Planar Graph Isomorphism is in Log-Space". 2009 24th Annual IEEE Conference on Computational Complexity. p. 203. doi:10.1109/CCC.2009.16. ISBN 978-0-7695-3717-7.  edit
  13. ^ Booth & Lueker 1979
  14. ^ Colbourn 1981
  15. ^ Bodlaender 1990
  16. ^ Miller 1980; Filotti & Mayer 1980.
  17. ^ Luks 1982
  18. ^ Babai, Grigoryev & Mount 1982
  19. ^ Gary L. Miller: Isomorphism Testing and Canonical Forms for k-Contractable Graphs (A Generalization of Bounded Valence and Bounded Genus). Proc. Int. Conf. on Foundations of Computer Theory, 1983, pp. 310–327 (Lecture Notes in Computer Science, vol. 158, full paper in: Information and Control, 56(1–2):1–20, 1983.)
  20. ^ Eugene Luks, "Parallel algorithms for permutation groups and graph isomorphism", Proc. IEEE Symp. Foundations of Computer Science, 1986, 292-302
  21. ^ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993
  22. ^ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
  23. ^ Arvind & Köbler 2000
  24. ^ a b c d e f g h i j k l m n o p q r s t u v w x Zemlyachenko, Korneenko & Tyshkevich 1985
  25. ^ "On the hardness of finding symmetries in Markov decision processes", by SM Narayanamurthy, B Ravindran, Proceedings of the Twenty Fifth International Conference on Machine Learning (ICML 2008), pp. 688–696.
  26. ^ D.Yu.Grigor'ev, "Complexity of “wild” matrix problems and of isomorphism of algebras and graphs", Journal of Mathematical Sciences, Volume 22, Number 3, 1983, pp. 1285–1289, doi:10.1007/BF01084390 (translation of a 1981 Russian language article)
  27. ^ a b c Volker Kaibel, Alexander Schwartz, "On the Complexity of Polytope Isomorphism Problems", Graphs and Combinatorics, 19 (2):215 —230, 2003.
  28. ^ Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25–29.
  29. ^ Kozen 1978.
  30. ^ J. Shawe-Taylor, T.Pisanski, "Homeomorphism of 2-Complexes is Graph Isomorphism Complete", SIAM Journal on Computing, 23 (1994) 120 – 132 .
  31. ^ R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131–132; Johnson 2005.
  32. ^ Designing Programs that Check their Work
  33. ^ Christophe-André Mario Irniger (2005) "Graph Matching: Filtering Databases of Graphs Using Machine Learning", ISBN 1-58603-557-6
  34. ^ "Mining Graph Data", by Diane J. Cook, Lawrence B. Holder (2007) ISBN 0-470-07303-9, pp. 120–122, section 6.2.1. "Canonical Labeling"
  35. ^ Baird, HS and Cho, YE (1975). "An artwork design verification system". Proceedings of the 12th Design Automation Conference. IEEE Press. pp. 414–420. 

References[edit]

Surveys and monographs[edit]

Software[edit]