Jump to content

Graph isomorphism problem

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dcoetzee (talk | contribs) at 19:57, 27 May 2005 (Write intro, what classes it's in, special cases, subgraph isomorphism problem, complement has zero-knowledge proofs, some references). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

In computational complexity theory, the graph isomorphism problem is the graph theory problem of determining whether, given two graphs G1 and G2, 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.

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 to be NP-complete. On the other hand, it's 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:

  • Isomorphisms of planar graphs can be found in linear time. Trees have a particularly simple algorithm.
  • Isomorphisms of graphs of bounded degree can be found in polynomial time.
  • 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, determining whether there are no isomorphisms between two graphs, 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.

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, pp. 310-324.
  • Luks E.M. Isomorphism of Graphs of Bounded Valence Can Be Tested in Polynomial Time, Proc. 21st IEEE FOCS Symp., 1980, pp. 42-49.
  • 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Graph_isomorphism_problem&oldid=14328620"