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)

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

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

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

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.

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

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.

that’s a good point actually.

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.

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

Pingback: Graph Isomorphism and Bounded Tree Width « My Brain is Open

Pingback: Hardness of Graph Isomorphism of Bounded TreeWidth Graphs « My Brain is Open

Pingback: Part II : Hardness of Graph Isomorphism of Bounded TreeWidth Graphs « My Brain is Open

Pingback: Computing Bounded Path Decompositions in Logspace « My Brain is Open

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.