Paper by Erik D. Demaine

Reference:

Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno, “On the Complexity of Reconfiguration Problems”, in Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008), Gold Coast, Australia, December 15–17, 2008, pages 28–39.

Abstract:

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.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (1134k) and PDF (176k).

See information on file formats.

[Google Scholar search]

Related papers:

NPReconfiguration_TCS (On the Complexity of Reconfiguration Problems)

NPReconfiguration_WADS2009 (Reconfiguration of List Edge-Colorings in a Graph)

SubsetSumReconfiguration_JOCO (Approximability of the Subset Sum Reconfiguration Problem)