Month: March 2011

by

Graph Isomorphism and Bounded Tree Width

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 k are also called partial k-trees. In 1992 Lindell proved that trees (graphs with treewidth=1) can be canonized in logspace [Lindel’92]. What about canonization for k=2 ? 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 k=3 ? Partial 3-trees may not be planar. An example is K_{3,3} itself. The tree width of K_{3,3} is three. I wanted to work on the case of k=3 and realized the following simple fact.

Exercise : Partial 3-trees are K_{5}-free.

In a follow-up paper to [DLNTW’09], Datta et al [DNTW’10] proved that canonization of K_{3,3}-free and K_{5}-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 k \geq 4. 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 k \geq 4) 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