Graph isomorphism

From Wikipedia, the free encyclopedia

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and 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.

If an isomorphism exists between two graphs, then the graphs are called isomorphic. 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 set of all graphs into equivalence classes. A set of graphs isomorphic to each other is called an isomorphism class of graphs.

Contents 1 Example 2 Motivation 3 Whitney graph isomorphism theorem 4 The graph isomorphism problem 5 Solved special cases 6 Complexity class GI 7 GI-Complete problems 7.1 Isomorphism of other objects 7.2 GI-complete classes of graphs 7.3 Other 8 Applications 9 See also 10 Notes 11 References 11.1 Surveys

[edit] 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

[edit] 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

may be different for two isomorphic graphs.

[edit] Whitney graph isomorphism theorem

The Whitney graph isomorphism theorem^[1], named after H. Whitney, gives a general condition for two graphs being isomorphic. The theorem is as follows: Let G and H be two simple, connected graphs, with an equal number of verticies and edges, and with at least three verticies. Let {E_i} be the set of edges of G, and {F_i} be the set of edges for H. Then, if

for all i and j, where the vertical bars denote the cardinality of a set (here, the cardinality of the set of verticies shared by pairs of edges), then G and H are isomorphic, with only one exception: G = K₃ is not isomorphic to H = K_1,3. More simply stated: if the line graphs of G and H are isomorphic, then with one exception G and H themselves are isomorphic.

Here, K₃ is the complete graph of three verticies, and K_1,3 is the complete bipartite graph with 1,3 vertices.

The Whitney graph theorem can be extended to hypergraphs.

[edit] The graph isomorphism problem

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 belonging to NP neither known to be solvable in polynomial time nor NP-complete. 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.^[2]

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

[edit] 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
  • Graphs of bounded genus^{[9] [10]}(Note: planar graphs are graphs of genus 0)
  • Graphs of bounded degree.^[11]
  • Graphs with bounded eigenvalue multiplicity.^[12]

[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.^[13] 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.^[14] 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.^[15] 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 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: ^[16]

• digraphs^[16]
• labelled graphs, with the proviso that an isomorphism is not required to preserve the labels, ^[16]but only the equivalence relation consisting of pairs of vertices with the same label
• 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)^[16]
• 2-colored graphs^[16]
• explicitly given finite structures^[16]
• multigraphs^[16]
• hypergraphs^[16]
• finite automata^[16]
• commutative class 3 nilpotent (i.e., xyz = 0 for every elements x, y, z) semigroups^[16]
• finite rank associative algebras over a fixed algebraically closed field with zero squared radical and commutative factor over the radical ^[16]
• context-free grammars^[16]
• balanced incomplete block designs^[16]

[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:^[16]

• connected graphs ^[16]
• graphs of diameter 2 and radius 1^[16]
• directed acyclic graphs ^[16]
• regular graphs. ^[16]
• bipartite graphs without non-trivial strongly regular subgraphs ^[16]
• bipartite Eulerian graphs ^[16]
• bipartite regular graphs ^[16]
• line graphs ^[16]
• chordal graphs ^[16]
• regular self-complementary graphs ^[16]
• graphs of general, simple, and simplicial polytopes in arbitrary dimensions^{[citation needed]}

Many classes of digraphs are also GI-complete.

[edit] Other

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

• The recognition of self-complementarity of a graph or digraph^[17]
• 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 ε. ^[18]

[edit] 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. ^[19] 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^[20]. 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.

Notice that molecular graphs have bounded degree (as the valence of any atom is at most 8), hence their isomorphism is testable in polynomial time^[21].

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

[edit] See also

• Graph homomorphism
• Graph automorphism problem

[edit] Notes

[edit] References