Today’s post is a continuation of earlier posts (here, here, here, here) on graph isomorphism, treewidth and pathwidth. As mentioned earlier, the best known upper bound for Graph Isomorphism of partial k-trees is LogCFL.
Theorem ([Das, Toran and Wagner’10]) : Graph isomorphism of bounded treewidth graphs is in LogCFL.
One of the bottlenecks of the algorithm of [DTW’10] is computing bounded tree decompositions in logspace. This is recently resolved by an amazing result of Elberfeld, Jakoby and Tantau [EJT’10]. The results in this paper are very powerful. Unfortunately, it is still not clear how to improve the LogCFL upper bound.
Can we improve the upper bound for special cases of partial k-trees ? How about bounded pathwidth graphs ? Again, one bottleneck here is to compute bounded path decompositions in logspace. [EJT’10]’s paper does not address this bottleneck and it is not clear how to extend their algorithm to compute path decompositions.
In joint work with Sinziana Munteanu, we resolved this bottleneck and proved the following theorem. Sinziana is a senior undergraduate student in our department. She is working with me on her senior thesis.
Theorem (Kintali, Munteanu’12) : For all constants
, there exists a logspace algorithm that, when given a graph
of treewidth
, decides whether the pathwidth of
, and if so, finds a path decomposition of
in logspace.
A draft of our results is available here. The above theorem is a logspace counterpart of the corresponding polynomial-time algorithm of [Bodlaender, Kloks’96]. Converting it into a logspace algorithm turned out to be a tedious task with some interesting tricks. Our work motivates the following open problem :
Open problem : What is the complexity of Graph Isomorphism of bounded pathwidth graphs ? Is there a logspace algorithm ?
Stay tuned for more papers related to graph isomorphism, treewidth and pathwidth. I am going through a phase of life, where I have more results than I can type. Is there an app that converts voice to latex ? Is there a journal that accepts hand-written proofs ? 🙂
My Brain is Open 