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 algorithms for the reconfiguration versions of

Vertex Cover

and, more generally,

Bounded Hitting Set

and

Feedback Vertex Set

, all parameterized by

k

. In contrast, we show that reconfiguring

Unbounded Hitting Set

is

W

[2]-hard when parameterized by

k

 + ℓ. We also demonstrate the

W

[1]-hardness of the reconfiguration versions of a large class of maximization problems parameterized by

k

 + ℓ, and of their corresponding 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

 + ℓ.