On the parameterized complexity of reconfiguration problems

We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration version of an optimization problem Q takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps that can be applied to transform S into T such that each step results in a feasible solution to Q. For most of the results in this paper, S and T are subsets of vertices of a given graph and a reconfiguration step adds or deletes a vertex. Our study is motivated by recent results establishing that for most NP-hard problems, the classical complexity of reconfiguration is PSPACE-complete. We address the question for several important graph properties under two natural parameterizations: k, the size of the solutions, and `, the length of the sequence of steps. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter al-gorithms for the reconfiguration versions of Vertex Cover and, more generally, Bounded Hitting Set and Feedback Vertex Set, all pa-rameterized by k. In contrast, we show that reconfiguring Unbounded Hitting Set is W [2]-hard when parameterized by k+`. We also demon-strate the W [1]-hardness of the reconfiguration versions of a large class of maximization problems parameterized by k + `, and of their corre-sponding deletion problems parameterized by `; in doing so, we show that there exist problems in FPT when parameterized by k, but whose reconfiguration versions are W [1]-hard when parameterized by k + `