Graph isomorphism

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

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

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.

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

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

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.
• Planar graphs.
• Interval graphs.
• Permutation graphs.
• Partial k-trees.
• Bounded-parameter graphs
  • Graphs of bounded genus (Note: planar graphs are graphs of genus 0)
  • Graphs of bounded degree.
  • Graphs with bounded eigenvalue multiplicity.

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. Problems this way equivalent to graph isomorphism are called GI-complete.

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. 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 ZPP^NP. 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 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.

• Digraphs
• Labelled graphs (graphs in which vertices with the same label are considered equivalent)
• Polarized graphs (made of a complete graph K_m and an empty graph K_n plus some edges connecting the two; their isomorphism must preserve the partition)
• Bicolored graphs
• Explicitly given finite structures, e.g., Tarski models
• Multigraphs
• Hypergraphs
• Finite automata
• Class 3 commutative nilpotent semigroups
• Finite rank associative algebras over a fixed algebraically closed field with zero squared radical and commutative factor over the radical
• Context-free grammars
• Balanced incomplete block designs

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.

• connected graphs
• graphs of diameter 2 and radius 1
• directed acyclic graphs
• regular graphs.
• Bipartite graphs without non-trivial strongly regular graphs
• Bipartite Eulerian graphs
• Bipartite regular graphs
• Line graphs
• Chordal graphs
• Regular self-complementary graphs

Many classes of digraphs are also GI-complete.

Other

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

• The recognition of self-complementarity of a graph or digraph
• 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 n². This fact is interesting because the problem of finding an n-ε-clique in a M-graph of size n² is NP-complete for arbitrarily small positive ε.

Applications

The graph isomorphism problem arises in a variety of practical applications. For example, in cheminformatics and in mathematical chemistry, graph isomorphism and other graph matching techniques are used to identify a chemical compound within a chemical database. Also, in organic mathematical chemistry graph isomorphism testing may be necessary for generation of molecular graphs and for computer synthesis. Regular graphs are the most difficult for such testing and many of them are very important for chemistry (for example, Cyclohexane, Benzene, Cuneane, Dodecahedrane etc.), but their part among chemical compounds is small, and decreases with increasing of number of vertices (i.e. number of atoms). Also, the majority of chemical structures are planar graphs. So, for many practical wide-distributed tasks (chemical database support etc.) special notations (for example, SMILES) or fast isomorphism testing for planar molecular graphs may be sufficient.

Another important application is in electronic design automation: graph isomorphism is the basis of the Layout Versus Schematic (LVS) circuit design verification.

See also

• Graph homomorphism

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

• 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)

• Miller, Gary (1980), Isomorphism testing for graphs of bounded genus, pp. 225–235, Proceedings of the 12th Annual ACM Symposium on Theory of Computing

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

graph isomorphism at PlanetMath.