next up previous contents index CD CD Algorithms
Next: Steiner Tree Up: Graph Problems: Hard Problems Previous: Edge Coloring

Graph Isomorphism

  

  figure17611

Input description: Two graphs, G and H.

Problem description: Find a (or all) mappings f of the vertices of G to the vertices of H such that G and H are identical; i.e. (x,y) is an edge of G iff (f(x),f(y)) is an edge of H.  

Discussion: Isomorphism is the problem of testing whether two graphs are really the same.   Suppose we are given a collection of graphs and must perform some operation on each of them. If we can identify which of the graphs are duplicates, they can be discarded so as to avoid redundant work.  

We need some terminology to settle what is meant when we say two graphs are the same. Two labeled graphs tex2html_wrap_inline29643 and tex2html_wrap_inline29645 are identical when tex2html_wrap_inline29647 iff tex2html_wrap_inline29649 .   The isomorphism problem consists of finding a mapping from the vertices of G to H such that they are identical. Such a mapping is called an isomorphism.

Identifying symmetries is another important application of graph isomorphism.   A mapping of a graph to itself is called an automorphism, and the collection of automorphisms (its automorphism group)   provides a great deal of information about symmetries in the graph. For example, the complete graph tex2html_wrap_inline29651 has n! automorphisms (any mapping will do), while an arbitrary random graph is likely to have few or perhaps only one, since G is always identical to itself.  

Several variations of graph isomorphism arise in practice:

No polynomial-time algorithm is known for graph isomorphism, but neither is it known to be NP-complete.   Along with integer factorization (see Section gif), it one of the few important algorithmic problems whose rough computational complexity is still not known.   The conventional wisdom is that isomorphism is a problem that lies between P and NP-complete if P tex2html_wrap_inline29667 NP.

Although no worst-case polynomial-time algorithm is known, testing isomorphism in practice is usually not very hard. The basic algorithm backtracks through all n! possible relabelings of the vertices of graph h with the names of vertices of graph g, and then tests whether the graphs are identical.   Of course, we can prune the search of all permutations with a given prefix as soon as we detect any mismatch between edges both of whose vertices are in the prefix.

However, the real key to efficient isomorphism testing is to preprocess the vertices into ``equivalence classes'', partitioning them   into sets of vertices such that two vertices in different sets cannot possibly be mistaken for each other. All vertices in each equivalence class must share the same value of some invariant that is independent of labeling.   Possibilities include:

Using these invariants, you should be able to partition the vertices of each graph into a large number of small equivalence classes. Finishing the job off with backtracking, using the name of each equivalence class as a label, should usually be quick work. If the sizes of the equivalence classes of both graphs are not identical, then the graphs cannot be isomorphic. It is harder to detect isomorphisms between graphs with high degrees of symmetry than it is for arbitrary graphs, because of the effectiveness of these equivalence-class partitioning heuristics.

Implementations: The world's fastest isomorphism testing program is Nauty, by Brendan D. McKay.   Nauty (No AUTomorphisms, Yes?) is a set of very efficient C language procedures for determining the automorphism group of a vertex-colored graph. Nauty is also able to produce a canonically labeled isomorph of the graph, to assist in isomorphism testing.   It was the basis of the first program to generate all the 11-vertex graphs without isomorphs, and can test most graphs of fewer than one hundred vertices in well under a second.   Nauty has been successfully ported to a variety of operating systems and C compilers. It may be obtained from http://cs.anu.edu.au/people/bdm/. It is free for educational and research applications, but for commercial use contact the author at bdm@cs.anu.edu.au.

Combinatorica [Ski90] provides (slow) Mathematica implementations of graph isomorphism and automorphism testing.     See Section gif for further information on Combinatorica.

Notes: Graph isomorphism is an important problem in complexity theory. Monographs on isomorphism detection include Hoffmann [Hof82].

Polynomial-time algorithms are known for planar graph isomorphism [HW74]   and for graphs where the maximum vertex degree is bounded by a constant [Luk80]. The all-pairs shortest path heuristic is due to [SD76], although there exist nonisomorphic graphs that realize the same set of distances [BH90]. A linear-time tree isomorphism algorithm for both labeled and unlabeled trees is presented in [AHU74].

A problem is said to be isomorphism-complete if it is provably as hard as isomorphism. Testing the isomorphism of bipartite graphs is   isomorphism-complete, since any graph can be made bipartite by replacing each edge by two edges connected with a new vertex. Clearly, the original graphs are isomorphic if and only if the transformed graphs are.

Related Problems: Shortest path (see page gif), string matching (see page gif).    


next up previous contents index CD CD Algorithms
Next: Steiner Tree Up: Graph Problems: Hard Problems Previous: Edge Coloring

Algorithms
Mon Jun 2 23:33:50 EDT 1997