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