Given a graph class H, the task of the H-SQUARE ROOT problem is to decide, whether an input graph G has a square root H that belongs to H. We are interested in the parameterized complexity of the problem for classes H 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 such that there is a modulator S of size κ 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 κ by providing algorithms with running time 2~(2~O(κ))· n~(O(1)). We further show that the running time of our algorithms is asymptotically optimal and it is unlikely that the double-exponential dependence on κ could be avoided. In particular, we prove that the VC-κ ROOT problem, that asks whether an input graph has a square root with vertex cover of size at most κ, cannot be solved in time 2~(2~O(κ))· n~(O(1)) unless the Exponential Time Hypothesis fails. Moreover, we point out that VC-κ ROOT parameterized by κ does not admit a subexponential kernel unless P=NP.
展开▼
