ECCC-Report TR09-094https://eccc.weizmann.ac.il/report/2009/094Comments and Revisions published for TR09-094en-usFri, 09 Oct 2009 20:59:44 +0200
Paper TR09-094
| Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs |
Bireswar Das,
Jacobo Toran,
Fabian Wagner
https://eccc.weizmann.ac.il/report/2009/094The 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}. Fri, 09 Oct 2009 20:59:44 +0200https://eccc.weizmann.ac.il/report/2009/094