If you read my earlier post, you known that I am fan of treewidth. Who isn’t !! The complexity of Graph Isomorphism (earlier post) is one of the long-standing open problem. Intersecting these two with one of my research interests (space-bounded computation) we get the following open problem :

Open Problem: What is the complexity of graph isomorphism for graphs with bounded treewidth ?

Graphs with treewidth at most are also called partial -trees. In 1992 Lindell proved that trees (graphs with treewidth=1) can be canonized in logspace [Lindel’92]. What about canonization for ? Recently Datta et. al [DLNTW’09] proved that the canonization of planar graph is logspace-complete. The following simple exercise shows that partial 2-trees are planar graphs. Hence the result of [DLNTW’09] implies that partial 2-trees can be canonized in logspace.

Exercise: Every partial 2-tree is planar.

In fact, canonization of partial 2-trees is settled earlier by [ADK’08]. What about ? Partial 3-trees may not be planar. An example is itself. The tree width of is three. I wanted to work on the case of and realized the following simple fact.

Exercise: Partial 3-trees are -free.

In a follow-up paper to [DLNTW’09], Datta et al [DNTW’10] proved that canonization of -free and -free graphs is in Log-space. Hence we get the following corollary :

Corollary: Partial 3-trees can be canonized in log-space.

Since the above result is not explicitly mentioned in any papers, I wanted to make it clear in this post. Hence the open problem is for . LogCFL is the best known upper bound for graph isomorphism of partial k-trees [DTW’10]. One of the bottleneck, finding a tree decomposition of partial k-tree in logspace, is resolved recently [EJT’10]. The above mentioned papers make use of a decomposition of the input graph into two- or three-connected subgraphs, constructing an appropriate tree of these subgraphs, using the known structural properties of two- and three-connected graphs to canonize these subgraphs and using Lindell’s result to canonize the entire graph. Unfortunately no clean characterization exists for graphs with connectivity at least four. Many long-standing open problems in graph theory are trivial for 2- and 3- connected graphs and open for higher connectivity. A clean characterization of 4-connected graphs seems to be a major bottleneck in improving the space complexity of canonization of partial 4-trees. I am lost :(

Open Problems

- Is graph isomorphism of partial k-trees (for ) in logspace ?
- Is canonization of partial k-trees in LogCFL ? The paper of [DTW’10] solves isomorphism only.

**References :**

**[Lindell’92]**Steven Lindell:**A Logspace Algorithm for Tree Canonization***STOC 1992: pages 400-404***[DLNTW’09]**Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:**Planar Graph Isomorphism is in Log-Space.***IEEE Conference on Computational Complexity 2009: 203-214***[DNTW’10]**Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner:**Graph Isomorphism for K{3, 3}-free and K5-free graphs is in Log-space.***Electronic Colloquium on Computational Complexity (ECCC) 17: 50 (2010)***[ADK’08]**Vikraman Arvind, Bireswar Das, Johannes Köbler:**A Logspace Algorithm for Partial 2-Tree Canonization.***CSR 2008: 40-51***[DTW’10]**Bireswar Das, Jacobo Torán, Fabian Wagner:**Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs.***STACS 2010: 227-238***[EJT’10]**Michael Elberfeld, Andreas Jakoby, Till Tantau:**Logspace Versions of the Theorems of Bodlaender and Courcelle.***FOCS 2010: 143-152*

Hi this is indeed a very interesting problem. Although my interest is more in the direction of time complexity than space complexity. I notice that you did not cite Bodlaender at all. He has worked on this topic and there is an old article on the topic:

Hans L. Bodlaender. Polynomial algorithms for chromatic index and graph isomorphism on partial k-trees. Journal of Algorithms 11(4): 631-643, 1990.

Where he shows that GI is polynomial on graphs of bounded treewidth.

I am not aware of any improvements to this runningtime. I think the runningtime he ended up with was n^(k+4.5).

Pingback: Graph Isomorphism, Tree Width, Path Width and LogSpace « My Brain is Open

Pingback: Hardness of Graph Isomorphism of Bounded TreeWidth Graphs « My Brain is Open

Pingback: Computing Bounded Path Decompositions in Logspace « My Brain is Open