On the complexity of reconfiguration problems

Reconfiguration 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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2011-03, Vol.412 (12), p.1054-1065
Main Authors: Ito, Takehiro, Demaine, Erik D., Harvey, Nicholas J.A., Papadimitriou, Christos H., Sideri, Martha, Uehara, Ryuhei, Uno, Yushi
Format: Article
Language:English
Subjects:
Applied sciences
Approximation
Complexity
Computer science
control theory
systems
Exact sciences and technology
Graph algorithm
Mathematical models
Miscellaneous
PSPACE-complete
Reachability on solution space
Reconfiguration
Theoretical computing
Transformations
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Reconfiguration 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2010.12.005