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:\; V(G)$
ightarrow V(H)
with the property that any two vertices ''u'' and ''v'' from ''G'' are adjacent if and only if ''f(u)'' and ''f(v)'' are adjacent in ''H''.
If an isomorphism can be constructed between two graphs, then we say those graphs are ''isomorphic''.
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 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 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.^[1]
A generalization of the problem, the subgraph isomorphism problem, is known to be NP-complete.

Contents

Example

Solved special cases

Complexity class GI

See also

Notes

References

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
		$f(a)\; =\; 1$$f(b)\; =\; 6$$f(c)\; =\; 8$$f(d)\; =\; 3$$f(g)\; =\; 5$$f(h)\; =\; 2$$f(i)\; =\; 4$$f(j)\; =\; 7$

Solved special cases

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

★ Trees.^[1]

★ Planar graphs.^[1]

★ Interval graphs.^[1]

★ Permutation graphs.^[1]

★ Partial k-trees.^[1]

★ Bounded-parameter graphs

★
★ Graphs of bounded genus^{[1] [1]}(Note: planar graphs are graphs of genus 0)

★
★ Graphs of bounded degree.^[1]

★
★ Graphs with bounded eigenvalue multiplicity.^[1]

Complexity class GI

Because the graph isomorphism problem is neither complete for any known classical class nor efficiently solvable, researchers 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.^[11]
'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.^[12]
GI is contained in and low for Parity P, as well as contained in the potentially much smaller class SPP.^[11] 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.^[1] 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

★ Graph homomorphism

Notes

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11. ;
12. .
13. ;
14.

References

★

★ .

★ .

★

★

★ .

★

★

★ 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

★

★ .

★ .

★ .

★ .

★ .

★

★