Every once in a while, I can’t help thinking about “the complexity of graph isomorphism for bounded treewidth graphs“. Today has been one of those days again. See my earlier post to get the context.
Theorem ([Das, Toran and Wagner'10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL.
The proof of the above theorem is as follows
- Graph isomorphism of bounded tree-distance width graphs is in L.
- Given two graphs and their tree decompositions, computing the isomorphism respecting these tree decompositions is reducible to (1).
- Given tree decomposition of only one graph, we can guess the tree decomposition of the other and guess the isomorphism (respecting the tree bags) and verify them using a non-deterministic auxiliary pushdown automata (a.k.a LogCFL).
- Since tree decomposition of a graph can be computed in LogCFL, the above theorem follows.
One of the bottlenecks, finding a tree decomposition of bounded treewidth graphs in logspace, is resolved by [Elberfeld, Jakoby and Tantau'10]. The following seems to be another major bottleneck.
Given a graphand a decomposition
, how fast can we verify that
The answer is frustratingly unknown. An even more frustrating realization I had today is that “it is not clear how to beat the LogDCFL upper bound for the more restricted path decomposition“. Even though the underlying tree in a path decomposition is just a path, verifying the connectivity conditions of a path decomposition does seem to require recursion. It is not clear how to avoid recursion.
I thought that logspace upper bound is possible. Now I am much less confident about logspace upper bound. I cannot waste more time on this.
The truth is “this is a cute problem“. I need to do something to take my mind off this problem and move on. Easy enough, except I need an idea.
Update (Oct 12 2011) : Noticed that verification of path decompositions is easy.
what’s “tree distance width” ?
See this paper for definition of tree distance width. http://arxiv.org/abs/1001.0383
A new, related, result:
http://arxiv.org/abs/1109.4910
Another new result for all graphs:
http://arxiv.org/abs/1004.1808
That’s a cute problem indeed. How hard is to verify, given a set of subsets of V, that they are the bags of a valid tree decomposition?
Pingback: Hardness of Graph Isomorphism of Bounded TreeWidth Graphs « My Brain is Open
Pingback: Computing Bounded Path Decompositions in Logspace « My Brain is Open