Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-053 | 13th July 2010 16:35

The Isomorphism Problem for $k$-Trees is Complete for Logspace

RSS-Feed

Abstract:

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.



Changes to previous version:

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.


Paper:

TR09-053 | 20th May 2009 00:00

The Isomorphism Problem for k-Trees is Complete for Logspace





TR09-053
Authors: Johannes Köbler, Sebastian Kuhnert
Publication: 2nd July 2009 11:13
Downloads: 2870
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint