# Hardness of Graph Isomorphism

The complexity of Graph Isomorphism (GI) is one of the major open problems. It is easy to see that $GI \in NP$. It is known that $GI \in NP \cap coAM$. The following theorem states that it is unlikely that GI is NP-complete.

Theorem [Schöning’87, BHZ’87] : If GI is NP-complete then the polynomial hierarchy collapses to its second level.

The counting version of GI is known to be reducible to its decisional version. A polynomial time algorithm solving GI would be a major breakthrough. The best known algorithm runs in $2^{O(\sqrt{n{\log}n})}$ for graphs with $n$ vertices. Several special cases are shown to be in P. Several problems are known to be GI-hard. See this wikipedia article for details. GI is widely believed to be an NP-intermediate problem.

Conjecture : If $P \neq NP$, then GI is neither NP-complete nor in P.

Note that if the above conjecture is true then GI is P-hard. Is GI known to be P-hard ? What is the best known hardness of GI ? Well… we know very little about the hardness of GI. The following exercises show that GI is L-hard.

Exercise : Consider the following restricted automorphism problem: Given a graph $G = (V,E)$ and two lists of nodes $(x_1, \dots, x_k),(y_1,\dots, y_k)$, is there an automorphism in G mapping $x_i$ to $y_i$ for 1 ≤ i ≤ k ? Show that this problem is reducible to GI.

Exercise : Show that Undirected ST-connectivity is reducible to the above mentioned automorphism problem.

Torán [Torán’00] proved the following hardness theorem. Informally speaking, GI is hard for all complexity classes defined in terms of the number of accepting computations of a nondeterministic logarithmic space machine. These are the best known hardness results for GI.

Theorem [Torán’00] : GI is hard for $NL$, $PL$, $Mod_k{L}$ and $DET$.

All these hardness results are under DLOGTIME uniform $AC^0$ many-one reductions. $DET$ is the class of problems $NC^1$ Turing reducible to the determinant [Cook’85]. It is known that $Mod_k{L} \subseteq DET$ and $NL \subseteq C_{=}L \subseteq PL \subseteq DET$. Hence the best known hardness of GI is DET-hardness. However, we do not know the exact complexity of $DET$ i.e., we don’t know where $DET$ lies in terms of the known complexity classes between $NL$ and $NC^2$. In particular, what is the relation between $LogCFL = SAC^1$ and $DET$ ?

Torán also showed a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. More details about the complexity of perfect matching in a future blog post.

Open Problems:

• Is GI LogCFL-hard ?
• Is DET LogCFL-hard ? What is the relation between LogCFL and DET ? This is an independent long-standing open problem. It deserves a separate blog post.
• Is $GI \in coNP$ ? A proof of this would imply that “if GI is NP-complete then $NP = coNP$“, improving the above mentioned theorem.
• Is GI in P for strongly regular graphs ? The best known algorithm for strongly regular graphs, given by Spielman [Spielman’96], runs in time $n^{O({n^{1/3}}{{\log}n})}$.

References :

• [BHZ’87] R. Boppana, J. Håstad, and S. Zachos , “Does co-NP have short interactive proofs?”, Information Processing Letters 25(2), pages 127-132, (1987).
• [Schöning’87] Uwe Schöning, Graph isomorphism is in the low hierarchy, Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312–323
• [Cook’85] Stephen A. Cook, A Taxonomy of Problems with Fast Parallel Algorithms Information and Control 64(1-3): 2-21 (1985)
• [Spielman’96] Daniel A. Spielman, Faster isomorphism testing of strongly regular graphsSTOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM, pp. 576–584
• [Torán’00] Jacobo Torán, On the Hardness of Graph Isomorphism. FOCS’2000, also: SIAM J. Comput. 33(5): 1093-1108 (2004)

## 14 thoughts on “Hardness of Graph Isomorphism”

1. Ravi Boppana |

I believe the theorem attributed to Schöning ’87 (if Graph Isomorphism is NP-complete, then the polynomial hierarchy collapses to its second level) was proved independently by Boppana, Håstad, and Zachos at the same time.

Reference: R. Boppana, J. Håstad, and S. Zachos (1987), “Does co-NP have short interactive proofs?”, Information Processing Letters 25, pages 127-132.

–Ravi Boppana

• kintali |

Hi Ravi, Thanks for pointing this. I updated the post.

2. luca |

One half of your conjecture is that if GI is in P, then P=NP. This would have to be proved by showing that a polynomial time algorithm for GI yields somehow a polynomial time algorithm for an NP-complete problem, and it’s hard to imagine how this could be demonstrated without proving that GI is NP-complete under, say, Cook-reductions (which I think is considered unlikely, although I don’t know if it’s also known to imply the collapse of the hierarchy).

3. Andy D |

Nice post!

Another useful reference is the book
‘The Graph Isomorphism Problem: Its Structural Complexity’, by
Kobler, Schöning, and Toran:

http://tiny.cc/0chr7

Just note that, being published in ’93, it doesn’t cover the more recent results.

4. Suresh |

It seems that the subexponential algorithm for GI is further evidence that it not being NPC ?

• Anonymous |

Suresh,

Is there any formal reason why a subexponential algorithm for GI implies that it is not NP-hard? A possible way to argue this would be to say that if there were a linear reduction from 3-SAT to GI (namely, a reduction that maps SAT instances with n variables to GI on n-node graphs), then a subexponential algorithm for GI implies a subexponential algorithm for 3-SAT which, I guess, would be rather surprising. But it is possible that the (supposed) NP-completeness reduction for GI might take n-variable SAT to n^100 node GI, and then this objection doesn’t hold any more.

• Suresh |

that’s a good point actually.

• V |

I wouldn’t take a subexponential algorithm as evidence that a problem is not NPC. Many problems for planar graphs are NPC but admit subexponential algorithms: e.g. planar vertex cover has a 2^{O(sqrt(n))} algorithm.

5. Michael Trofimov |

Following may be interesting: “Polynomial Time Algorithm for Graph Isomorphism Testing” http://arxiv.org/abs/1004.1808

6. Jarod Benowitz |

I’m presenting a proof that GI is in P on tuesday. It was an accidental discovery (if it is correct) and began with finding an analogue to Feynman’s Path Integral on graphs.