Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR09-094 | 7th October 2009 14:30

Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs


Authors: Bireswar Das, Jacobo Toran, Fabian Wagner
Publication: 9th October 2009 20:59
Downloads: 3354


The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width
are known to be solvable in polynomial time \cite{Bo90},\cite{YBFT}.
We give restricted space algorithms for these problems proving the following results:

Isomorphism for bounded tree distance width graphs is in L and thus complete for the class. We also show that for this kind of graphs a canon
can be computed within logspace.

For bounded treewidth graphs, when both input graphs are given together with a tree decomposition,
the problem of whether there is an isomorphism respecting the decompositions is in L.

For bounded treewidth graphs, when one of the input graphs is given with a tree decomposition
the isomorphism problem is in LogCFL.

As a corollary the isomorphism problem for bounded treewidth graphs is in LogCFL. This improves the
known TC^1 upper bound for the problem given by Grohe and Verbitsky \cite{GV06}.

ISSN 1433-8092 | Imprint