# 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)