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.

### Like this:

Like Loading...

*Related*

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