PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
From MaRDI portal
Publication:2570127
DOI10.1016/j.tcs.2005.05.008zbMath1079.68040arXivcs/0205005OpenAlexW2036722182MaRDI QIDQ2570127
Erik D. Demaine, Robert A. Hearn
Publication date: 26 October 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0205005
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (94)
\textsc{Pull} and \textsc{PushPull} are PSPACE-complete ⋮ Push-Pull Block Puzzles are Hard ⋮ Decremental Optimization of Dominating Sets Under the Reconfiguration Framework ⋮ The complexity of Snake and undirected NCL variants ⋮ On the Complexity of an Unregulated Traffic Crossing ⋮ The Complexity of Dominating Set Reconfiguration ⋮ TS-reconfiguration of dominating sets in circle and circular-arc graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ Complexity of Hamiltonian cycle reconfiguration ⋮ Reconfiguration of List Edge-Colorings in a Graph ⋮ Invitation to combinatorial reconfiguration ⋮ Traversability, reconfiguration, and reachability in the gadget framework ⋮ Reconfiguration of dominating sets ⋮ Reconfiguration on nowhere dense graph classes ⋮ Reconfiguration graphs of shortest paths ⋮ Shortest reconfiguration of sliding tokens on subclasses of interval graphs ⋮ Rerouting shortest paths in planar graphs ⋮ Congestion-Free Rerouting of Flows on DAGs ⋮ Vertex Cover Reconfiguration and Beyond ⋮ Reconfiguration of Vertex Covers in a Graph ⋮ Pushing lines helps: efficient universal centralised transformations for programmable matter ⋮ PSPACE-Completeness of Bloxorz and of Games with 2-Buttons ⋮ The complexity of rerouting shortest paths ⋮ Fixed-parameter algorithms for graph constraint logic ⋮ Token sliding on graphs of girth five ⋮ Reconfiguration in bounded bandwidth and tree-depth ⋮ Reconfiguration of spanning trees with degree constraints or diameter constraints ⋮ Feedback vertex set reconfiguration in planar graphs ⋮ Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs ⋮ Finding Paths between Graph Colourings: Computational Complexity and Possible Distances ⋮ On the complexity of distance-\(d\) independent set reconfiguration ⋮ Reconfiguration of connected graph partitions ⋮ Galactic token sliding ⋮ Parameterized complexity of independent set reconfiguration problems ⋮ 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids ⋮ Token sliding on graphs of girth five ⋮ Extremal independent set reconfiguration ⋮ Digraph redicolouring ⋮ Particle computation: complexity, algorithms, and logic ⋮ Defying gravity and gadget numerosity: the complexity of the Hanano puzzle ⋮ On the complexity of reconfiguration problems ⋮ Computational complexity of jumping block puzzles ⋮ Complexity of independent set reconfigurability problems ⋮ Reconfiguration of cliques in a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Scheduling Autonomous Vehicle Platoons Through an Unregulated Intersection ⋮ Unnamed Item ⋮ The Complexity of (List) Edge-Coloring Reconfiguration Problem ⋮ Sliding Tokens on Block Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Reconfiguration of Spanning Trees with Many or Few Leaves ⋮ Shortest Paths between Shortest Paths and Independent Sets ⋮ Approximability of the subset sum reconfiguration problem ⋮ The kissing problem: how to end a gathering when everyone kisses everyone else goodbye ⋮ On girth and the parameterized complexity of token sliding and Token Jumping ⋮ Linear-time algorithm for sliding tokens on trees ⋮ On the transformation capability of feasible mechanisms for programmable matter ⋮ Approximability of the Subset Sum Reconfiguration Problem ⋮ An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree ⋮ The complexity of dominating set reconfiguration ⋮ Reconfiguration of list \(L(2,1)\)-labelings in a graph ⋮ \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete ⋮ On the parameterized complexity of reconfiguration problems ⋮ Traversability, reconfiguration, and reachability in the gadget framework ⋮ Reconfiguration of list edge-colorings in a graph ⋮ Shortest paths between shortest paths ⋮ Unnamed Item ⋮ Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles ⋮ Reconfiguration of satisfying assignments and subset sums: easy to find, hard to connect ⋮ Reconfiguring spanning and induced subgraphs ⋮ Dominating sets reconfiguration under token sliding ⋮ Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch ⋮ Computational complexity of jumping block puzzles ⋮ Shortest Reconfiguration of Sliding Tokens on a Caterpillar ⋮ Independent-set reconfiguration thresholds of hereditary graph classes ⋮ Homomorphism Reconfiguration via Homotopy ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Diameter of colorings under Kempe changes ⋮ Token sliding on split graphs ⋮ Unnamed Item ⋮ Independent Set Reconfiguration in Cographs and their Generalizations ⋮ The Perfect Matching Reconfiguration Problem ⋮ Reconfiguration of Minimum Steiner Trees via Vertex Exchanges ⋮ Reconfiguration of connected graph partitions via recombination ⋮ Reconfiguration of connected graph partitions via recombination ⋮ Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances ⋮ Reconfiguration of Colorable Sets in Classes of Perfect Graphs ⋮ Introduction to reconfiguration ⋮ DYNAMIC POINT LABELING IS STRONGLY PSPACE-COMPLETE ⋮ On reconfigurability of target sets ⋮ Complexity of Coloring Reconfiguration under Recolorability Constraints
Cites Work
This page was built for publication: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
