On the parallel parameterized complexity of the graph isomorphism problem

Abstract

In this paper, we study the parallel and the space complexity of the graph isomorphism problem (\GI{}) for several parameterizations. Let H={H1,H2,?,Hl} be a finite set of graphs where |V(Hi)|?d for all i and for some constant d. Let G be an H-free graph class i.e., none of the graphs G?G contain any H?H as an induced subgraph. We show that \GI{} parameterized by vertex deletion distance to G is in a parameterized version of $\AC^1$, denoted $\PL$-$\AC^1$, provided the colored graph isomorphism problem for graphs in G is in $\AC^1$. From this, we deduce that \GI{} parameterized by the vertex deletion distance to cographs is in $\PL$-$\AC^1$. The parallel parameterized complexity of \GI{} parameterized by the size of a feedback vertex set remains an open problem. Towards this direction we show that the graph isomorphism problem is in $\PL$-$\TC^0$ when parameterized by vertex cover or by twin-cover. Let G? be a graph class such that recognizing graphs from G? and the colored version of \GI{} for G? is in logspace ($\L$). We show that \GI{} for bounded vertex deletion distance to G? is in $\L$. From this, we obtain logspace algorithms for \GI{} for graphs with bounded vertex deletion distance to interval graphs and graphs with bounded vertex deletion distance to cographs.