| Graph Isomorphism Problem |
Article Index for Graph |
Website Links For Graph |
Information AboutGraph Isomorphism Problem |
|
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''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:
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 System s, 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'''. 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 Graph s and Regular Graph s. It also has nontrivial complete problems in addition to isomorphism problems, such as a variation on the Maximum Clique Problem defined by Dexter Kozen. 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. REFERENCES
EXTERNAL LINKS |
|
|