Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-032 | 11th March 2011 14:36

Graphs of Bounded Treewidth can be Canonized in AC$^1$


Authors: Fabian Wagner
Publication: 13th March 2011 22:09
Downloads: 3226


In recent results the complexity of isomorphism testing on
graphs of bounded treewidth is improved to TC$^1$ [GV06] and further to LogCFL [DTW10].
The computation of canonical forms or a canonical labeling provides more information than
isomorphism testing.
Whether canonization is in NC or even TC$^1$ was stated as an open question in [Köb06].
Köbler and Verbitsky [KV08] give a TC$^2$ canonical labeling algorithm.
We show that a canonical labeling can be computed in AC$^1$.
This is based on several ideas,
e.g. that approximate tree decompositions of logarithmic depth can be obtained in logspace [EJT10],
and techniques of Lindells tree canonization algorithm [Lin92].
We define recursively what we call a minimal description which gives with respect to some parameters
in a logarithmic number of levels a canonical invariant together with an arrangement of all vertices.
From this we compute a canonical labeling.

ISSN 1433-8092 | Imprint