Graph isomorphism

This MedLibrary.org supplementary page on Graph isomorphism is provided directly from the open source Wikipedia as a service to our readers. Please see the note below on authorship of this content, as well as the Wikipedia usage guidelines. To search for other content from our encyclopedia supplement, please use the form below:

Related Sponsors

BM Pharmacy Generic pharmaceuticals at unbeatable prices. Insomnia, men's health, hair health, pain control. bmpharmacy.com
Online Pharmacy Carisoprodol, tadalafil, sildenafil, vardenafil and more... xlpharmacy.com
MedBasket.com Discreet. Inexpensive. Fast shipping. Great selection. What more can we say? medbasket.com
Frugalmed 2000 reasons to shop with us first. frugalmed.com
Ads by Tiva

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H

f \colon V(G) \to V(H) \,\!

such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.

In the above definition graphs are understood to be undirected non-labeled non-weighted graphs, however the notion of isomorphism may be applied to all of these, by adding the requirements to preserve the corresponding additional elements of structure: arc directions, edge weights, etc., with the following exception. When spoken about graph labeling with unique labels, commonly taken from the integer range 1,...,n, where n is the number of the vertices of the graph, two labeled graphs are said to be isomorphic if the corresponding underlying unlabeled graphs are isomorphic.

If an isomorphism exists between two graphs, then the graphs are called isomorphic and we write G\simeq 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.

The graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs.

Contents

Example

The two graphs shown below are isomorphic, despite their different looking drawings.

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

Motivation

The formal notion of "isomorphism", e.g., of "graph isomorphism", captures the informal notion that some objects have "the same structure" if one ignores individual distinctions of "atomic" components of objects in question, see the example above. Whenever individuality of "atomic" components (vertices and edges, for graphs) is important for correct representation of whatever is modeled by graphs, the model is refined by imposing additional restrictions on the structure, and other mathematical objects are used: digraphs, labeled graphs, colored graphs, rooted trees and so on. The isomorphism relation may also be defined for all these generalizations of graphs: the isomorphism bijection must preserve the elements of structure which define the object type in question: arcs, labels, vertex/edge colors, the root of the rooted tree, etc.

The notion of "graph isomorphism" allows us to distinguish graph properties inherent to the structures of graphs themselves from properties associated with graph representations: graph drawings, data structures for graphs, graph labelings, etc. For example, if a graph has exactly one cycle, then all graphs in its isomorphism class also have exactly one cycle. On the other hand, in the common case when the vertices of a graph are (represented by) the integers 1, 2,... N, then the expression

\sum_{v \in V(G)} v\cdot\text{deg }v

may be different for two isomorphic graphs.

Whitney theorem

The exception of Whitney's theorem: these two graphs are not isomorphic but have isomorphic line graphs.

The Whitney graph isomorphism theorem,1 shown by H. Whitney, states that two connected graphs are isomorphic if and only if their line graphs are isomorphic, with a single exception: K3, the complete graph on three vertices, and the complete bipartite graph K1,3, which are not isomorphic but both have K3 as their line graph. The Whitney graph theorem can be extended to hypergraphs.2

The graph isomorphism problem

The computational problem of determining whether two finite graphs are isomorphic is referred to as the graph isomorphism problem.

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. As of 2005 the best algorithm (Babai & Luks, 1983) has run time 2^{O(\sqrt {(n \log n)}\;)} for graphs with n vertices.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

A generalization of the problem, the subgraph isomorphism problem, is known to be NP-complete.

Solved special cases

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

Example: Rooted trees

There is a particularly simple algorithm for determining if two rooted trees T and T' are isomorphic. First, assume that T and T' have the same number of vertices and the same height (otherwise they are not isomorphic). The vertices can be grouped into levels, sets of vertices that are the same distance from the root; since distance from the root is preserved by isomorphism, vertices in T must correspond to vertices in T' at the same level. We process the tree beginning with the bottom level and moving upwards, systematically assigning a label to each vertex such that two vertices have the same label if and only if the subtrees rooted at those two vertices are isomorphic.

Suppose v is an unlabelled vertex. Since the algorithm processes the tree bottom-up, all its children already have labels; assign v a temporary long label by sorting and concatenating the labels of its children. Next, sort all vertices at the current level by their long labels; then, assign fresh short labels to each vertex by numbering them from zero and giving identically-labelled vertices the same number. If at any level the final sorted set of short labels is different in T and T', then they are not isomorphic; otherwise the two roots will be assigned the same label and they are isomorphic.

Sorting the labels with a simple comparison sort, this algorithm requires Θ(n log n) time, where n is the number of vertices; it can be made to operate in O(n) time by careful use of bucket sort and radix sort.

This algorithm can be used to find isomorphism of general trees by noting that an isomorphism must map the center of T to the center of T'; the center of a tree has at most two vertices, so there are at most two ways of selecting the root nodes.

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.17 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.18 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.19 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: 20

This list is incomplete; you can help by expanding it.

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:20

This list is incomplete; you can help by expanding it.

Many classes of digraphs are also GI-complete.

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 digraph23
  • 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 ε. 24
  • The problem of counting the number of isomorphisms between two graphs is polynomial-time equivalent to the problem of telling whether even one exists2526

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. 21

Applications

In cheminformatics and in mathematical chemistry, graph isomorphism testing is used to identify a chemical compound within a chemical database. 27 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.28 In particular, 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.29

See also

Notes

  1. ^ H. Whitney, "Congruent graphs and the connectivity of graphs", Am. J. Math., 54(1932) pp. 160-168.
  2. ^ Dirk L. Vertigan, Geoffrey P. Whittle: A 2-Isomorphism Theorem for Hypergraphs. J. Comb. Theory, Ser. B 71(2): 215-230. 1997.
  3. ^ Johnson 2005
  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. ^ P.J. Kelly, "A congruence theorem for trees" Pacific J. Math., 7 (1957) pp. 961–968
  7. ^ Aho, Hopcroft & Ullman 1974
  8. ^ Hopcroft & Wong 1974
  9. ^ Booth & Lueker 1979
  10. ^ Colbourn 1981
  11. ^ Bodlaender 1990
  12. ^ Miller 1980
  13. ^ Filotti & Mayer 1980
  14. ^ Luks 1982
  15. ^ Babai, Grigoryev & Mount 1982
  16. ^ 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.)
  17. ^ Booth & Colbourn 1977; Köbler, Schöning & Torán 1993
  18. ^ Köbler, Schöning & Torán 1992; Arvind & Kurur 2006
  19. ^ Arvind & Köbler 2000
  20. ^ 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
  21. ^ a b c Volker Kaibel, Alexander Schwartz, "On the Complexity of Polytope Isomorphism Problems", Graphs and Combinatorics, 19 (2):215 —230, 2003.
  22. ^ Johnson 2005
  23. ^ Colbourn M.J., Colbourn Ch.J. "Graph isomorphism and self-complementary graphs", SIGACT News, 1978, vol. 10, no. 1, 25-29
  24. ^ Kozen 1978.
  25. ^ R. Mathon, "A note on the graph isomorphism counting problem", Information Processing Letters, 8 (1979) pp. 131-132
  26. ^ Johnson 2005
  27. ^ Christophe-André Mario Irniger (2005) "Graph Matching: Filtering Databases of Graphs Using Machine Learning", ISBN 1586035576
  28. ^ "Mining Graph Data", by Diane J. Cook, Lawrence B. Holder (2007) ISBN 0470073039, pp. 120–122, section 6.2.1. "Canonical Labeling"
  29. ^ Carl Ebeling, "Gemini II: A Second Generation Layout Validation Tool", IEEE International Conference on Computer Aided Design (ICCAD-88), pp. 322-325, November 1988

References

  • 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:10.1016/j.ic.2006.02.002 .
  • Bodlaender, Hans (1990), "Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees", Journal of Algorithms 11: 631–643, doi:10.1016/0196-6774(90)90013-5 
  • Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo .
  • 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
  • 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, OCLC 246882287 .
  • 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, doi:10.1016/0022-0000(82)90009-5 .

Surveys and monographs

Wikipedia content modification information:

  • This page was last modified on 6 January 2009, at 20:15.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Graph isomorphism".

The URL for this specific entry is:

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.