Computing Bounded Path Decompositions in Logspace

Today’s post is a continuation of earlier posts (here, here, here, here) on graph isomorphism, treewidth and pathwidth. As mentioned earlier, the best known upper bound for Graph Isomorphism of partial k-trees is LogCFL.

Theorem ([Das, Toran and Wagner’10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL.

One of the bottlenecks of the algorithm of [DTW’10] is computing bounded tree decompositions in logspace. This is recently resolved by an amazing result of Elberfeld, Jakoby and Tantau [EJT’10]. The results in this paper are very powerful. Unfortunately, it is still not clear how to improve the LogCFL upper bound.

Can we improve the upper bound for special cases of partial k-trees ? How about bounded pathwidth graphs ? Again, one bottleneck here is to compute bounded path decompositions in logspace. [EJT’10]’s paper does not address this bottleneck and it is not clear how to extend their algorithm to compute path decompositions.

In joint work with Sinziana Munteanu, we resolved this bottleneck and proved the following theorem. Sinziana is a senior undergraduate student in our department. She is working with me on her senior thesis.

Theorem (Kintali, Munteanu’12) : For all constants $k, l \geq 1$, there exists a logspace algorithm that, when given a graph $G$ of treewidth $\leq l$, decides whether the pathwidth of $G$ is at most $k$, and if so, finds a path decomposition of $G$ of width $\leq k$ in logspace.

A draft of our results is available here. The above theorem is a logspace counterpart of the corresponding polynomial-time algorithm of [Bodlaender, Kloks’96]. Converting it into a logspace algorithm turned out to be a tedious task with some interesting tricks. Our work motivates the following open problem :

Open problem : What is the complexity of Graph Isomorphism of bounded pathwidth graphs ? Is there a logspace algorithm ?

Stay tuned for more papers related to graph isomorphism, treewidth and pathwidth. I am going through a phase of life, where I have more results than I can type. Is there an app that converts voice to latex ? Is there a journal that accepts hand-written proofs ? 🙂

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