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 (Gl) for several parameterizations. Let H = {H_1,H_2, …, H_l} be a finite set of graphs where | V(H_i)|≤ 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 Gl parameterized by vertex deletion distance to G is in a parameterized version of AC~1, denoted Para-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 Para-AC~1. The parallel parameterized complexity of Gl 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 Para-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 Gl for G' is in logspace (L). We show that Gl for bounded vertex deletion distance to G' is in L. From this, we obtain logspace algorithms for Gl for graphs with bounded vertex deletion distance to interval graphs and graphs with bounded vertex deletion distance to cographs.