The complexity of Graph Isomorphism (GI) is one of the major open problems. It is easy to see that . It is known that . 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 for graphs with 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 , 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 and two lists of nodes , is there an automorphism in G mapping to 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 , , and .

All these hardness results are under DLOGTIME uniform many-one reductions. is the class of problems Turing reducible to the determinant [Cook’85]. It is known that and . Hence the best known hardness of GI is DET-hardness. However, we do not know the exact complexity of i.e., we don’t know where lies in terms of the known complexity classes between and . In particular, what is the relation between and ?

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 ? A proof of this would imply that “if GI is NP-complete then “, 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 .

*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 graphs**,*STOC ’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)