Graph isomorphism problem
From Wikipedia, the free encyclopedia
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.[1] As of 2005[update] the best algorithm (Babai & Luks, 1983) has run time 2O(√(n log n)) for graphs with n vertices.[2]
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.[3]
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.[4]
A generalization of the problem, the subgraph isomorphism problem, is known to be NP-complete.
Contents |
[edit] Solved special cases
A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:
- Trees[5]
- Planar graphs[6]
- Interval graphs[7]
- Permutation graphs[8]
- Partial k-trees[9]
- Bounded-parameter graphs
[edit] Complexity class GI
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.[14] If in fact the graph isomorphism problem is solvable in polynomial time, GI would equal P.
As it 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 P 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 P.
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.[15] 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.[16] 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.
[edit] GI-complete and GI-hard problems
[edit] 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:[17]
- digraphs[17]
- labelled graphs, with the proviso that an isomorphism is not required to preserve the labels,[17] but only the equivalence relation consisting of pairs of vertices with the same label
- "polarized graphs" (made of a complete graph Km and an empty graph Kn plus some edges connecting the two; their isomorphism must preserve the partition)[17]
- 2-colored graphs[17]
- explicitly given finite structures[17]
- multigraphs[17]
- hypergraphs[17]
- finite automata[17]
- Markov Decision Processes[18]
- commutative class 3 nilpotent (i.e., xyz = 0 for every elements x, y, z) semigroups[17]
- finite rank associative algebras over a fixed algebraically closed field with zero squared radical and commutative factor over the radical[17][19]
- context-free grammars[17]
- balanced incomplete block designs[17]
- Recognizing combinatorial isomorphism of convex polytopes represented by vertex-facet incidences.[20][21]
[edit] 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:[17]
- connected graphs[17]
- graphs of diameter 2 and radius 1[17]
- directed acyclic graphs[17]
- regular graphs.[17]
- bipartite graphs without non-trivial strongly regular subgraphs[17]
- bipartite Eulerian graphs[17]
- bipartite regular graphs[17]
- line graphs[17]
- chordal graphs[17]
- regular self-complementary graphs[17]
- polytopal graphs of general, simple, and simplicial convex polytopes in arbitrary dimensions[20]
Many classes of digraphs are also GI-complete.
[edit] Other GI-complete problems
There are other nontrivial GI-complete problems in addition to isomorphism problems.
- The recognition of self-complementarity of a graph or digraph.[22]
- A clique problem for a class of so-called M-graphs. It is shown that finding of 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 ε.[23]
- The problem of counting the number of isomorphisms between two graphs is polynomial-time equivalent to the problem of telling whether even one exists.[24]
[edit] GI-hard problems
- 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.[20]
[edit] Applications
In cheminformatics and in mathematical chemistry, graph isomorphism testing is used to identify a chemical compound within a chemical database.[25] 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.[26] 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.[27]
[edit] See also
[edit] Notes
- ^ The latest one resolved was minimum weight triangulation, proved to be NP-complete in 2008.Mulzer, Wolfgang; Rote, Günter, "Minimum-weight triangulation is NP-hard", Journal of the ACM 55 (2), doi:, arΧiv:cs.CG/0601002.
- ^ Johnson 2005
- ^ 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
- ^ McKay 1981
- ^ P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957) pp. 961–968; Aho, Hopcroft & Ullman 1974.
- ^ Hopcroft & Wong 1974
- ^ Booth & Lueker 1979
- ^ Colbourn 1981
- ^ Bodlaender 1990
- ^ Miller 1980; Filotti & Mayer 1980.
- ^ Luks 1982
- ^ Babai, Grigoryev & Mount 1982
- ^ 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.)
- ^ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993
- ^ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
- ^ Arvind & Köbler 2000
- ^ 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
- ^ "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.
- ^ 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)
- ^ a b c Volker Kaibel, Alexander Schwartz, "On the Complexity of Polytope Isomorphism Problems", Graphs and Combinatorics, 19 (2):215 —230, 2003.
- ^ Johnson 2005
- ^ Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25–29.
- ^ Kozen 1978.
- ^ R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131–132; Johnson 2005.
- ^ Christophe-André Mario Irniger (2005) "Graph Matching: Filtering Databases of Graphs Using Machine Learning", ISBN 1586035576
- ^ "Mining Graph Data", by Diane J. Cook, Lawrence B. Holder (2007) ISBN 0470073039, pp. 120–122, section 6.2.1. "Canonical Labeling"
- ^ Carl Ebeling, "Gemini II: A Second Generation Layout Validation Tool", IEEE International Conference on Computer Aided Design (ICCAD-88), pp. 322–325, November 1988
[edit] References
- Aho, Alfred V.; Hopcroft, John; Ullman, Jeffrey D. (1974), The Design and Analysis of Computer Algorithms, Reading, MA: Addison–Wesley
- Arvind, Vikraman; Köbler, Johannes (2000), "Graph isomorphism is low for ZPP(NP) and other lowness results.", Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Springer-Verlag, Lecture Notes in Computer Science 1770, pp. 431–442, ISBN 3-540-67141-2, OCLC 43526888.
- Arvind, Vikraman; Kurur, Piyush P. (2006), "Graph isomorphism is in SPP", Information and Computation 204 (5): 835–852, doi:.
- Babai, László; Grigoryev, D. Yu.; Mount, David M. (1982), Isomorphism of graphs with bounded eigenvalue multiplicity, pp. 310–324, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, http://portal.acm.org/citation.cfm?id=802206&dl=ACM&coll=portal
- Bodlaender, Hans (1990), "Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees", Journal of Algorithms 11: 631–643, doi:
- Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo.
- Booth, Kellogg S.; Lueker, George S. (1979), "A linear time algorithm for deciding interval graph isomorphism", Journal of the ACM 26 (2): 183–195, doi:
- Boucher, C.; Loker, D. (2006), Graph isomorphism completeness for perfect graphs and subclasses of perfect graphs, University of Waterloo, Technical Report CS-2006-32, http://www.cs.uwaterloo.ca/research/tr/2006/CS-2006-32.pdf
- Colbourn, C. J. (1981), "On testing isomorphism of permutation graphs", Networks 11: 13–21, doi:
- I. S. Filotti , Jack N. Mayer (1980), A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, p.236–243
- Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 978-0716710455, OCLC 11745039
- Hopcroft, John; Wong, J. (1974), "Linear time algorithm for isomorphism of planar graphs", Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 172–184, doi:.
- Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity 2 (4): 301–330, doi:.
- Köbler, Johannes; Schöning, Uwe; Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0817636807, OCLC 246882287.
- Kozen, Dexter (1978), "A clique problem equivalent to graph isomorphism", ACM SIGACT News 10 (2): 50–52, doi:.
- Luks, Eugene M. (1982), "Isomorphism of graphs of bounded valence can be tested in polynomial time", Journal of Computer and System Sciences 25: 42–65, doi:.
- McKay, Brendan D. (1981), "Practical graph isomorphism", Congressus Numerantium 30: 45–87, 10th. Manitoba Conference on Numerical Mathematics and Computing (Winnipeg, 1980), http://cs.anu.edu.au/~bdm/nauty/PGI/
- Miller, Gary (1980), Isomorphism testing for graphs of bounded genus, pp. 225–235, Proceedings of the 12th Annual ACM Symposium on Theory of Computing, http://portal.acm.org/citation.cfm?id=804670&dl=ACM&coll=portal
[edit] Surveys and monographs
- Ronald Read and Derek Corneil. "The graph isomorphism disease". Journal of Graph Theory 1977, 1, 339–363
- Gati, G. "Further annotated bibliography on the isomorphism disease." – Journal of Graph Theory 1979, 3, 95–109
- Zemlyachenko, V. N.; Korneenko, N. M. and Tyshkevich, R. I. (1985). "Graph isomorphism problem". Journal of Mathematical Sciences 29 (4): 1426–1481. doi:. (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118, pp. 83–158, 1982.)
- Arvind, V.; Jacobo Torán (1985). "Isomorphism Testing: Perspectives and Open Problems". Bulletin of the European Association for Theoretical Computer Science (no. 86): 66–84. (A brief survey of open questions related to the isomorphism problem for graphs, rings and groups)
- Köbler, Johannes; Uwe Schöning, Jacobo Torán (1993). Graph Isomorphism Problem: The Structural Complexity. Birkhäuser Verlag. ISBN 0817636803. OCLC 246882287. (From the book cover: The books focuses on the issue of the computational complexity of the problem and presents several recent results that provide a better understanding of the relative position of the problem in the class NP as well as in other complexity classes.)
- Johnson, David S. (2005), "The NP-Completeness Column", ACM Transactions on Algorithms 1 (no. 1): 160–176, doi: (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism)
[edit] Software
- Graph Isomorphism, review of implementations, The Stony Brook Algorithm Repository.
