Given a graph class , the task of the -Square Root problem is to decide whether an input graph G has a square root H that belongs to . We are interested in the parameterized complexity of the problem for classes that are composed by the graphs at vertex deletion distance at most from graphs of maximum degree at most one. That is, we are looking for a square root H that has a modulator S of size k such that H-S is the disjoint union of isolated vertices and disjoint edges. We show that different variants of the problems with constraints on the number of isolated vertices and edges in H-S are FPT when parameterized by k, by providing algorithms with running time . We further show that the running time of our algorithms is asymptotically optimal and it is unlikely that the double-exponential dependence on k could be avoided. In particular, we prove that the VC-k Root problem, that asks whether an input graph has a square root with vertex cover of size at most k, cannot be solved in time unless the Exponential Time Hypothesis fails. Moreover, we point out that VC-k Root parameterized by k does not admit a subexponential kernel unless P=NP.
This is a joint work with Petr Golovach and Charis Papadopoulos.