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 graph and a decomposition , how fast can we verify that is a valid tree decomposition of ? The upper bound of LogDCFL (the deterministic version of LogCFL) is clear from the above mentioned results. Can this verification be done in logspace ?

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.

Advertisements

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