Graph isomorphism problem

From Wikipedia, the free encyclopedia

In computational complexity theory, the graph isomorphism problem or GI problem is the graph theory problem of determining whether, given two graphs G₁ and G₂, it is possible to permute (or relabel) the vertices of one graph so that it is equal to the other. Such a permutation is called a graph isomorphism. Put another way, the graph isomorphism problem asks whether two graphs can be drawn with identical graph drawings.

The graph isomorphism is of critical importance in a variety of practical problems. One application that arises in both chemical research and circuit design is building 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 solving a variety of practical problems, the graph isomorphism problem is a curiosity in complexity theory for defying the typical classifications that apply to other interesting practical problems. It is in NP, since the proof certificate is a permutation of the vertices which makes the graphs equal, but it is not known or believed to be NP-complete. In fact, R.B. Boppana et al. have shown that if graph isomorphism is NP-complete, the polynomial hierarchy collapses to $\Pi^P_2$ , and most researchers believe this hierarchy does not collapse at all.

On the other hand, graph isomorphism is also not known to be in any practical class such as P, RP, or BPP, and so is still considered to be a hard problem although there is not strong theoretical support for this. It is also not known to be in co-NP.

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

Planar graphs: linear time. Trees have a particularly simple algorithm.
Graphs of bounded degree
Interval graphs
Permutation graphs
Convex graphs
A number of other more complex special cases.

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

The complement of the graph isomorphism problem, sometimes called the graph nonisomorphism problem, is in co-NP, and was one of the first problems shown to be solvable by interactive proof systems, as well as one of the first problems for which a zero-knowledge proof was exhibited. This was exhibited as evidence of the power of such systems, since this problem is not known to be in NP.

[edit] The 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. With this definition, the problem is trivially a complete problem for GI.

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 defined by Dexter Kozen. It is also contained in Parity P (and in fact in the potentially much smaller class SPP[1]), meaning 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.

The class GI is contained in, and in fact 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.

[edit] References

Hopcroft J., Wong J. A Linear Time Algorithm for Isomorphism of Planar Graphs, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, 1974, pp. 310-324.
Luks E.M. Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time, Proc. 21st IEEE FOCS Symp., 1982, Vol. 25, pp. 42-65.
Kellogg S. Booth and C.J. Colbourn. Problems Polynomially Equivalent to Graph Isomorphism. Technical Report CS-77-04, Computer Science Department, University of Waterloo. 1979.
O. Goldreich, S. Micali, A. Wigderson. Proofs that yield nothing but their validity. Journal of the ACM, volume 38, issue 3, p.690-728. July 1991.
J. Köbler, U. Schöning, and J. Torán. The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser, 1993. ISBN.
Dexter Kozen. A clique problem equivalent to graph isomorphism. ACM SIGACT News archive, volume 10, issue 2, p.50-52. Summer 1978.
R. B. Bopanna, J. Hastad, and S. Zachos. Does co-NP have short interactive proofs?. Inform. Process. Lett. volume 25, p.127-133. 1987.