In graph theory, a graph isomorphism is a bijection (a one-to-one and onto mapping) between the vertices of two graphs G and H
- <math> f \colon V(G) \to V(H) \,\!</math>
with the property that any two vertices u and v from G are adjacent if and only if ƒ(u) and ƒ(v) are adjacent in H. If an isomorphism can be constructed between two graphs, then the graphs are called isomorphic. The bijection in question is called an isomorphism of G and H. In the case when the bijection is a mapping of a graph onto itself, i.e., when G and H are one and the same graph, the bijection is called an automorphism of G. Determining whether two graphs are isomorphic is referred to as the graph isomorphism problem. The graph isomorphism problem arises in a variety of practical applications. In both chemical research[1] and circuit design it is important to build databases of graphs; in this case, we wish to know if a new graph we are entering is the same as one that is already present, to save storage and detect correspondences between data. Besides its importance for these applications, the graph isomorphism problem is a curiosity in computational complexity theory as it is one of a very small number of problems listed by Garey & Johnson (1979) as belonging to NP, but neither known to be in polynomial time nor NP-complete, although isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently.[2] A generalization of the problem, the subgraph isomorphism problem, is known to be NP-complete.
Contents |
Example
The two graphs shown below are isomorphic, despite their very different looking drawings, due to the existence of the bijection described to the right.
| Graph G | Graph H | An isomorphism between G and H |
|---|---|---|
 |
 |
ƒ(a) = 1
ƒ(b) = 6 ƒ(c) = 8 ƒ(d) = 3 ƒ(g) = 5 ƒ(h) = 2 ƒ(i) = 4 ƒ(j) = 7 |
Solved special cases
A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions:
- Trees.[3][4]
- Planar graphs.[5]
- Interval graphs.[6]
- Permutation graphs.[7]
- Partial k-trees.[8]
- Bounded-parameter graphs
Complexity class GI
Because 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.[13] GI is contained in both NP and co-AM. Graph isomorphism remains GI-complete even when restricted to a number of "hard" special cases, such as directed acyclic graphs and regular graphs. It also has nontrivial complete problems in addition to isomorphism problems, such as a variation on the maximum clique problem.[14] 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.
See also
Notes
- ^ M.I.Trofimov, E.A.Smolenskii, Russian Chemical Bulletin, 2005, Vol. 54, 9, 2235. (http://dx.doi.org/10.1007/s11172-006-0105-6)
- ^ 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
- ^ Booth & Colbourn 1979; Köbler, Schöning & Torán 1993
- ^ Kozen 1978.
- ^ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
- ^ Arvind & Köbler 2000
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.
- Arvind, Vikraman & Kurur, Piyush P. (2006), "Graph isomorphism is in SPP", Information and Computation 204 (5): 835–852, DOI 10.1016/j.ic.2006.02.002.
- 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
- Booth, Kellogg S. & Colbourn, C. J. (1979), 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 10.1145/322123.322125
- Colbourn, C. J. (1981), "On testing isomorphism of permutation graphs", Networks 11: 13–21
- 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
- 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 10.1145/800119.803896.
- Köbler, Johannes; Schöning, Uwe & Torán, Jacobo (1992), "Graph isomorphism is low for PP", Computational Complexity 2 (4): 301–330, DOI 10.1007/BF01200427.
- Köbler, Johannes; Schöning, Uwe & Torán, Jacobo (1993), The Graph Isomorphism Problem: Its Structural Complexity, Birkhäuser, ISBN 978-0817636807.
- Kozen, Dexter (1978), "A clique problem equivalent to graph isomorphism", ACM SIGACT News 10 (2): 50–52, DOI 10.1145/990524.990529.
- 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.
- 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>
Surveys
- 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." – J. of Graph Theory, 3 (1979), 95-109
- V. N. Zemlyachenko, N. M. Korneenko and R. I. Tyshkevich, "Graph isomorphism problem", " Journal of Mathematical Sciences", Vol. 29, no. 4, 1985, pp. 1426-1481 doi:10.1007/BF02104746 (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 118, pp. 83–158, 1982.)
This article incorporates material from graph isomorphism on PlanetMath, which is licensed under the GFDL.
