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. In computer science, computational complexity theory is the branch of the theory of computation that studies the resources required during computation to solve a given problem. ... A diagram of a graph with 6 vertices and 7 edges. ... In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. ... As a branch of Graph theory, Graph drawing applies topology and geometry to derive visual and haptic representations of graphs. ...

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 ismorphism is NP-complete, the polynomial hierarchy collapses to Π^p₂, and most researchers believe this hierarchy does not collapse at all. In computational complexity theory, NP (Non-deterministic Polynomial time) is the set of decision problems solvable in polynomial time on a non-deterministic Turing machine. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines. ...

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. In computational complexity theory, P is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. ... This article relates to the theory of computation. ... This article is about the complexity class. ...

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. In graph theory, a planar graph is a graph that can be embedded in a plane so that no edges intersect. ... In the mathematical field of graph theory the degree or valency of a vertex v is the number of edges incident to v (with loops being counted twice). ... In graph theory, an interval graph is a graph that captures the intersections among a set of intervals on the real line. ... In complexity theory, Subgraph-Isomorphism is a decision problem that is known to be NP-complete. ... In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use...

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 believed to even be in NP. In computational complexity theory, the complement of a decision problem is the decision problem resulting from reversing the yes and no answers. ... In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. ... In cryptography, a zero-knowledge proof is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement. ...

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. In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. ...

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. In computational complexity theory, an Arthur-Merlin protocol is an interactive proof system in which the verifiers coin tosses are constrained to be public (i. ... A simple directed acyclic graph In mathematics, a directed acyclic graph, also called a dag or DAG, is a directed graph with no directed cycles; that is, for any vertex v, there is no directed path starting and ending on v. ... In graph theory, a regular graph is a graph where each vertex has the same number of neighbors, i. ... In computational complexity theory, the clique problem or k-clique problem is a graph-theoretical NP-complete problem. ...

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. It is also low for Parity P, meaning that it is similarly a much easier problem than determining whether a polynomial-time nondeterministic Turing machine has an even or odd number of accepting paths. In computational complexity theory, it is said that a complexity class B is low for a complexity class A if AB = A; that is, A with an oracle for B is equal to A. Such a statement implies that an abstract machine which solves problems in A achieves no additional... In complexity theory, ZPP (Zero-error Probabilistic Polynomial time) is the set of problems for which a probabilistic Turing machine exists with these properties: It always returns the correct YES or NO answer. ... In computing, a Las Vegas algorithm is a randomized algorithm which is correct; that is, it always produces the correct result. ... In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. ... In computational complexity theory, the complexity class ⊕P (pronounced parity P) is the class of decision problems solvable by a nondeterministic Turing machine in polynomial time, where the acceptance condition is that the number of accepting computation paths is odd. ... In theoretical computer science, an ordinary (deterministic) Turing machine has a transition rule that specifies for a given current state of the head and computer (s,q) a single instruction (s, q, d), where s is the symbol to be written by the head, q is the subsequent state of...

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.
• 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 0-8176-3680-3.
• 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.

External links

• Mathworld. Isomorphic Graphs.
• Complexity Zoo: GI