Title: 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
$\mathcal{H}=\{H_1,H_2,\cdots,H_l\}$ be a finite set of graphs where
$|V(H_i)|\leq d$ for all $i$ and for some constant $d$. Let $\mathcal{G}$ be an
$\mathcal{H}$-free graph class i.e., none of the graphs $G\in \mathcal{G}$
contain any $H \in \mathcal{H}$ as an induced subgraph. We show that \GI{}
parameterized by vertex deletion distance to $\mathcal{G}$ is in a
parameterized version of $\AC^1$, denoted $\PL$-$\AC^1$, provided the colored
graph isomorphism problem for graphs in $\mathcal{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 $\mathcal{G}'$ be a graph class such that recognizing graphs from
$\mathcal{G}'$ and the colored version of \GI{} for $\mathcal{G}'$ is in
logspace ($\L$). We show that \GI{} for bounded vertex deletion distance to
$\mathcal{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.