by

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”

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

    Reply

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

    Reply

    • 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

    • 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

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

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

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

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

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

    Reply

Leave a comment