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.

*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 ?

**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.

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.