TY - GEN

T1 - On the parameterized complexity of reconfiguration problems

AU - Mouawad, Amer E.

AU - Nishimura, Naomi

AU - Raman, Venkatesh

AU - Simjour, Narges

AU - Suzuki, Akira

PY - 2013/12/1

Y1 - 2013/12/1

N2 - 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 + ℓ.

AB - 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 + ℓ.

UR - http://www.scopus.com/inward/record.url?scp=84893134615&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84893134615&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-03898-8_24

DO - 10.1007/978-3-319-03898-8_24

M3 - Conference contribution

AN - SCOPUS:84893134615

SN - 9783319038971

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 281

EP - 294

BT - Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Revised Selected Papers

T2 - 8th International Symposium on Parameterized and Exact Computation, IPEC 2013

Y2 - 4 September 2013 through 6 September 2013

ER -