Revision #1 Authors: Vikraman Arvind, Bireswar Das, Sebastian Kuhnert, Johannes Köbler

Accepted on: 13th July 2010 16:35

Downloads: 1909

Keywords:

We show that, for $k$ constant, $k$-tree isomorphism can be decided in logarithmic space by giving a logspace canonical labeling algorithm. The algorithm computes a unique tree decomposition, uses colors to fully encode the structure of the original graph in the decomposition tree and invokes Lindell's tree canonization algorithm. As a consequence, the isomorphism, the automorphism, as well as the canonization problem for $k$-trees are all complete for deterministic logspace. Completeness for logspace holds even for simple structural properties of $k$-trees. We also show that isomorphism of all $k$-trees, $k\ge 1$, is fixed parameter tractable with respect to $k$ by giving an algorithm running in time $O((k+2)!\cdot m)$, where $m$ is the number of edges in the input graph.

This revision includes the relevant parts of the intermediate StUL result of Arvind, Das, and Koebler, introducing Arvind and Das as co-authors. Also, the hardness results are improved and a section is added that describes an FPT algorithm for k-tree canonization with k as parameter.

TR09-053 Authors: Johannes Köbler, Sebastian Kuhnert

Publication: 2nd July 2009 11:13

Downloads: 1978

Keywords:

We show that k-tree isomorphism can be decided in logarithmic

space by giving a logspace canonical labeling algorithm. This improves

over the previous StUL upper bound and matches the lower bound. As a

consequence, the isomorphism, the automorphism, as well as the

canonization problem for k-trees are all complete for deterministic

logspace. We also show that even simple structural properties of k-trees

are complete for logspace.