Graph isomorphism problem

This article describes a decision problem from or related to graph theory. The problem is mentioned in this wiki due to its close relation with computational and decision problems in computational group theory

Description

Given data

Two graphs $X_{1}=(V_{1},E_{1})$ and $X_{2}=(V_{2},E_{2})$ specified in some standard format (such as incidence matrix, adjacency matrix etc.)

By graph here we mean finite simple undirected graph, though, by suitable equivalences and reductions, we can consider directed graphs and allow loops and parallel edges.

Goal

We need to determine whether $X_{1}$ and $X_{2}$ are isomorphic as abstract finite simple undirected graphs.

Relation with other problems

Problems it reduces to

• Graph automorphism-finding problem: This problem takes as input a graph and outputs a generating set for the automorphism group of the graph. The graph isomorphism problem reduces to the graph automorphism-finding problem as follows: Let $X_{1}$ and $X_{2}$ be the two graphs we need to check for isomorphism. There are three possibilities:

• • $X_{1}$ and $X_{2}$ are both connected. In this case, consider the graph $X$ defined as the disjoint union of $X_{1}$ and $X_{2}$, and determine a generating set for the automorphism group of $X$. Then, $X_{1}$ and $X_{2}$ are isomorphic as graphs if and only if $X$ contains an element that takes an element of $X_{1}$ to within $X_{2}$.

• • One of $X_{1}$ and $X_{2}$ is connected but the other isn't: In this case, $X_{1}$ and $X_{2}$ are not isomorphic.

• • Neither of $X_{1}$ nor $X_{2}$ is connected. In this case, we switch to the complements both of $X_{1}$ and $X_{2}$ and apply the first step to those complements (we use the fact that two graphs are isomorphic if and only if their complements are).

Problems that reduce to it

• Graph automorphism-testing problem: This problem asks, given a graph, whether it has a nontrivial automorphism. It turns out that by being able to test whether two graphs are isomorphic, we can determine whether a given graph has a nontrivial automorphism.

Particular graph isomorphism problems

Given a graph property $p$ which can be easily tested for a graph from its adjacency matrix, we are interested in the graph isomorphism problem for the situation where both graphs are guaranteed to have property $p$.

Particular cases of this, which have been solved, are:

• Tree isomorphism problem: Here, both graphs are trees
• Forest isomorphism problem: Here, both graphs are forests
• Bounded degree graph isomorphism problem: Here the valency of the graph, viz the maximum of degrees of all its vertices, is specified

Isomorphism problems for graphs with additional structure

Some problems of graphs with additional structure:

• Bounded colour graph isomorphism problem: Here, we assign a colour to each vertex (using the same colour pool for both graphs) and call the graphs isomorphic if there is an isomorphism between them that takes each vertex to another of the same colour.

Current knowledge state of complexity classes

Complexity classes it is contained in

Complexity classes in or related to the polynomial hierarchy:

• Non-deterministic polynomial time: Given two graphs that are isomorphic, we can explicitly construct an isomorphism between them by specifying where it sends each vertex. Further, given a candidate isomorphism, checking that it is actually an isomorphism requires only polynomial time (we need to check for every pair of vertices whether the relation of being adjacent is preserved).

• co-AM: Given two graphs, we can construct an Arthur-Merlin game for graph non-isomorphism. Here's a simple description: suppose Merlin wants to prove to Arthur that two graphs $X_{1}$ and $X_{2}$ are non-isomorphic. Clearly, if the sizes of the graphs are not equal, then Merlin can just use size to prove to Arthur. Suppose now that $X_{1}$ and $X_{2}$ are both graphs of size $n$. Then, Arthur flips a coin and picks one of $X_{1}$ and $X_{2}$. Further, Arthur chooses a random permutation and sends across the $X_{i}$ that he has picked with the vertices permuted according to that permutation.

Merlin's job now is to determine which of the graphs Arthur had chosen. If the graphs are indeed non-isomorphic, Merlin should (given his infinite computational power) be able to uniquely pinpoint the graph.

In fact, this proves that graph non-isomorphism is in AM[2].

• co-IP[2]: Graph non-isomorphism can also be solved in the public coin Arthur-Merlin protocol in two steps (this uses the idea of hashing).

• Statistical zero knowledge: It is possible to give a proof of the fact that two graphs are isomorphic without giving any information about how the isomorphism arises.

• L₂(P): This follows from the fact that graph isomorphism is in both NP and co-AM.

Deterministic complexity classes:

Complexity classes it is conjectured to be in

Complexity classes related to the polynomial hierarchy:

• co-NP: So far, graph isomorphism has only been shown to be in co-AM (which is R.co-NP). It is strongly believe d that graph isomorphism is actually in co-NP.

In fact, the class of problems many-one reducible to graph isomorphism is believed to be strictly contained in NP ∩ co-NP.

Deterministic complexity classes: