Month: September 2010

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)