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

14 thoughts on “Hardness of Graph Isomorphism”

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 | September 2, 2010 at 6:14 PM

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

Reply

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 ?

Anonymous | September 2, 2010 at 11:16 PM

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.

Reply
- Suresh | September 3, 2010 at 1:02 AM
  
  that’s a good point actually.
V | September 3, 2010 at 3:52 PM

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.

Reply

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.

My Brain is Open

Computational Complexity, Polyhedral Combinatorics, Algorithms and Graph Theory

Hardness of Graph Isomorphism

14 thoughts on “Hardness of Graph Isomorphism”

Leave a Reply Cancel reply

Share this:

Like this:

Related

14 thoughts on “Hardness of Graph Isomorphism”

Leave a Reply Cancel reply