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”, Theoretical Computer Science, volume 412, number 12–14, 2011, pages 1054–1065.

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

Length:

The paper is 12 pages.

Availability:

The paper is available in PDF (451k).

See information on file formats.

[Google Scholar search]

Related papers:

NPReconfiguration_ISAAC2008 (On the Complexity of Reconfiguration Problems)

SubsetSumReconfiguration_JOCO (Approximability of the Subset Sum Reconfiguration Problem)

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