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)|\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 $\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}}^{\prime }$ be a graph class such that recognizing graphs from ${\mathcal{G}}^{\prime }$ and the colored version of \GI{} for ${\mathcal{G}}^{\prime }$ is in logspace ($Ł$). We show that \GI{} for bounded vertex deletion distance to ${\mathcal{G}}^{\prime }$ is in $Ł$. 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.