Graph isomorphism problem
≈ 10 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently. This problem is a special case of the subgraph isomorphism problem, which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H; this problem is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group. In the area of image recognition it is known as the exact graph matching problem.
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic. The problem is not known to be solvable in polynomial time nor to be NP-complete, and therefore may be in the computational complexity class NP-intermediate. It is known that the graph isomorphism problem is in the low hierarchy of class NP, which implies that it is not NP-complete unless the polynomial time hierarchy collapses to its second level. At the same time, isomorphism for many special classes of graphs can be solved in polynomial time, and in practice graph isomorphism can often be solved efficiently. This problem is a special case of the subgraph isomorphism problem, which asks whether a given graph G contains a subgraph that is isomorphic to another given graph H; this problem is known to be NP-complete. It is also known to be a special case of the non-abelian hidden subgroup problem over the symmetric group. In the area of image recognition it is known as the exact graph matching problem.
State of the art
In November 2015, László Babai announced a quasi-polynomial time algorithm for all graphs, that is, one with running time 2^{O((\log n)^c)} for some fixed c > 0 . On January 4, 2017, Babai retracted the quasi-polynomial claim and stated a sub-exponential time bound instead after Harald Helfgott discovered a flaw in the proof. On January 9, 2017, Babai announced a correction (published in full on January 19) and restored the quasi-polynomial claim, with Helfgott confirming the fix. Helfgott further claims that one can take , so the running time is . Babai published a "preliminary report" on related work at the 20191 Symposium on Theory of Computing, describing a quasipolynomial algorithm for graph canonization, but the full version of these algorithms remains unpublished. Prior to this, the best accepted theoretical algorithm was due to , and was based on the earlier work by combined with a subfactorial algorithm of V. N. Zemlyachenko . The algorithm has run time 2 O( ) for graphs with n vertices and relies on the classification of finite simple groups. Without this classification theorem, a slightly weaker bound was obtained first for strongly regular graphs by , and then extended to general graphs by . Improvement of the exponent for strongly regular graphs was done by . For hypergraphs of bounded rank, a subexponential upper bound matching the case of graphs was obtained by . There are several competing practical algorithms for graph isomorphism, such as those due to , , , and . While they seem to perform well on random graphs, a major drawback of these algorithms is their exponential time performance in the worst case. The graph isomorphism problem is computationally equivalent to the problem of computing the automorphism group of a graph, and is weaker than the permutation group isomorphism problem and the permutation group intersection problem. For the latter two problems, obtained complexity bounds similar to that for graph isomorphism.
Solved special cases
A number of important special cases of the graph isomorphism problem have efficient, polynomial-time solutions: Trees Planar graphs (In fact, planar graph isomorphism is in log space, a class contained in P) Interval graphs Permutation graphs Circulant graphs Bounded-parameter graphs Graphs of bounded treewidth Graphs of bounded genus (Planar graphs are graphs of genus 0.) Graphs of bounded degree Graphs with bounded eigenvalue multiplicity k-Contractible graphs (a generalization of bounded degree and bounded genus) Color-preserving isomorphism of colored graphs with bounded color multiplicity (i.e., at most k vertices have the same color for a fixed k) is in class NC, which is a subclass of P.
GI-complete and GI-hard problems
Isomorphism of other objects
There are a number of classes of mathematical objects for which the problem of isomorphism is a GI-complete problem. A number of them are graphs endowed with additional properties or restrictions: digraphs labelled graphs, with the proviso that an isomorphism is not required to preserve the labels, but only the equivalence relation consisting of pairs of vertices with the same label "polarized graphs" (made of a complete graph K m and an empty graph K n plus some edges connecting the two; their isomorphism must preserve the partition) 2-colored graphs explicitly given finite structures multigraphs hypergraphs finite automata Markov Decision Processes commutative class 3 nilpotent (i.e., xyz = 0 for every elements x, y, z) semigroups finite rank associative algebras over a fixed algebraically closed field with zero squared radical and commutative factor over the radical. context-free grammars normal-form games balanced incomplete block designs Recognizing combinatorial isomorphism of convex polytopes represented by vertex-facet incidences.
GI-complete classes of graphs
A class of graphs is called GI-complete if recognition of isomorphism for graphs from this subclass is a GI-complete problem. The following classes are GI-complete: connected graphs graphs of diameter 2 and radius 1 directed acyclic graphs regular graphs bipartite graphs without non-trivial strongly regular subgraphs bipartite Eulerian graphs bipartite regular graphs line graphs split graphs chordal graphs regular self-complementary graphs polytopal graphs of general, simple, and simplicial convex polytopes in arbitrary dimensions. Many classes of digraphs are also GI-complete.
Other GI-complete problems
There are other nontrivial GI-complete problems in addition to isomorphism problems. Finding a graph's automorphism group. Counting automorphisms of a graph. The recognition of self-complementarity of a graph or digraph. A clique problem for a class of so-called M-graphs. It is shown that finding an isomorphism for n-vertex graphs is equivalent to finding an n-clique in an M-graph of size n 2 . This fact is interesting because the problem of finding a clique of order (1 − ε)n in a M-graph of size n 2 is NP-complete for arbitrarily small positive ε. The problem of homeomorphism of 2-complexes. The definability problem for first-order logic. The input of this problem is a relational database instance I and a relation R, and the question to answer is whether there exists a first-order query Q (without constants) such that Q evaluated on I gives R as the answer.
GI-hard problems
The problem of counting the number of isomorphisms between two graphs is polynomial-time equivalent to the problem of telling whether even one exists. The problem of deciding whether two convex polytopes given by either the V-description or H-description are projectively or affinely isomorphic. The latter means existence of a projective or affine map between the spaces that contain the two polytopes (not necessarily of the same dimension) which induces a bijection between the polytopes.
Program checking
have shown a probabilistic checker for programs for graph isomorphism. Suppose P is a claimed polynomial-time procedure that checks if two graphs are isomorphic, but it is not trusted. To check if graphs G and H are isomorphic: Ask P whether G and H are isomorphic. If the answer is "yes": Attempt to construct an isomorphism using P as subroutine. Mark a vertex u in G and v in H, and modify the graphs to make them distinctive (with a small local change). Ask P if the modified graphs are isomorphic. If no, change v to a different vertex. Continue searching. Either the isomorphism will be found (and can be verified), or P will contradict itself. If the answer is "no": Perform the following 100 times. Choose randomly G or H, and randomly permute its vertices. Ask P if the graph is isomorphic to G and H. (As in AM protocol for graph nonisomorphism). If any of the tests are failed, judge P as invalid program. Otherwise, answer "no". This procedure is polynomial-time and gives the correct answer if P is a correct program for graph isomorphism. If P is not a correct program, but answers correctly on G and H, the checker will either give the correct answer, or detect invalid behaviour of P. If P is not a correct program, and answers incorrectly on G and H, the checker will detect invalid behaviour of P with high probability, or answer wrong with probability 2 −100 . Notably, P is used only as a blackbox.
See also
Graph automorphism problem Graph canonization
Notes
References
. . . . . . . . . . . . . . . . . . . . . . . . English translation in Journal of Mathematical Sciences 22 (3): 1285–1289, 1983. . . . . . . . . . . . . Full paper in Information and Control 56 (1–2): 1–20, 1983. . . . . ; also Journal of Computer and System Sciences 37: 312–323, 1988. . . .
Surveys and monographs
. . . (Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (Records of Seminars of the Leningrad Department of Steklov Institute of Mathematics of the USSR Academy of Sciences), Vol. 118, pp. 83–158, 1982.) . (A brief survey of open questions related to the isomorphism problem for graphs, rings and groups.) . (From the book cover: The books focuses on the issue of the computational complexity of the problem and presents several recent results that provide a better understanding of the relative position of the problem in the class NP as well as in other complexity classes.) . (This 24th edition of the Column discusses the state of the art for the open problems from the book Computers and Intractability and previous columns, in particular, for Graph Isomorphism.) . .
Software
Graph Isomorphism, review of implementations, The Stony Brook Algorithm Repository.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1350231769 under CC BY-SA 4.0; modifications have been made.