On the Parallel Parameterized Complexity of the Graph Isomorphism Problem

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 $\mathrm{\mid }V(H_i)\mathrm{\mid }\le 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 ${\text{AC}}^1$, denoted $\text{PL}$-${\text{AC}}^1$, provided the colored graph isomorphism problem for graphs in $\mathcal{G}$ is in ${\text{AC}}^1$. From this, we deduce that \GI{} parameterized by the vertex deletion distance to cographs is in $\text{PL}$-${\text{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 $\text{PL}$-${\text{TC}}^0$ when parameterized by vertex cover or by twin-cover. Let ${\mathcal{G}}^{\mathrm{\prime }}$ be a graph class such that recognizing graphs from ${\mathcal{G}}^{\mathrm{\prime }}$ and the colored version of \GI{} for ${\mathcal{G}}^{\mathrm{\prime }}$ is in logspace ($\text{L}$). We show that \GI{} for bounded vertex deletion distance to ${\mathcal{G}}^{\mathrm{\prime }}$ is in $\text{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.