On the complexity of reconfiguration problems

• DOI: 10.1016/j.tcs.2010.12.005
• Publication Date: 2010-12-15T04:29:24Z
• Authors: Takehiro Ito; Erik D. Demaine; Nicholas J.A. Harvey; Christos H. Papad...; Martha Sideri; Ryuhei Uehara; Yushi Uno
• Keywords: Control reconfiguration; NP-complete

AbstractReconfiguration problems arise when we wish to find a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. We demonstrate that a host of reconfiguration problems derived from NP-complete problems are PSPACE-complete, while some are also NP-hard to approximate. In contrast, several reconfiguration versions of problems in P are solvable in polynomial time.