TR09-094 Authors: Bireswar Das, Jacobo Toran, Fabian Wagner

Publication: 9th October 2009 20:59

Downloads: 3051

Keywords:

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}.