TY - JOUR

T1 - On the Parameterized Complexity of Reconfiguration Problems

AU - Mouawad, Amer E.

AU - Nishimura, Naomi

AU - Raman, Venkatesh

AU - Simjour, Narges

AU - Suzuki, Akira

N1 - Funding Information:
Research of the first, second, and fourth authors is supported by the Natural Science and Engineering Research Council of Canada. Research of the fifth author is supported by JSPS Grant-in-Aid for Scientific Research, Grant Number 26730001.
Publisher Copyright:
© 2016, Springer Science+Business Media New York.

PY - 2017/5/1

Y1 - 2017/5/1

N2 - We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem Q takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, 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 sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many 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, a bound on the size of solutions, and ℓ, a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants 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 reconfiguration variants 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 variants are W[1]-hard when parameterized by k+ ℓ.

AB - We present the first results on the parameterized complexity of reconfiguration problems, where a reconfiguration variant of an optimization problem Q takes as input two feasible solutions S and T and determines if there is a sequence of reconfiguration steps, i.e. a reconfiguration sequence, 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 sets of vertices of a given graph and a reconfiguration step adds or removes a vertex. Our study is motivated by results establishing that for many 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, a bound on the size of solutions, and ℓ, a bound on the length of reconfiguration sequences. Our first general result is an algorithmic paradigm, the reconfiguration kernel, used to obtain fixed-parameter tractable algorithms for reconfiguration variants 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 reconfiguration variants 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 variants are W[1]-hard when parameterized by k+ ℓ.

KW - Hitting set

KW - Parameterized complexity

KW - Reconfiguration

KW - Solution space

KW - Vertex cover

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

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

U2 - 10.1007/s00453-016-0159-2

DO - 10.1007/s00453-016-0159-2

M3 - Article

AN - SCOPUS:84966687086

VL - 78

SP - 274

EP - 297

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 1

ER -