2026-07-25T06:06:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23064 2025-10-02T12:32:46Z ddc:004 open_access

Hardness of Traversing Gadget Systems with Small Bandwidth MIT Gadgets Group Demaine, Erik D. Diomidova, Jenny Gomez, Timothy Hecher, Markus Lynch, Jayson Gadgets Motion Planning Parameterized Complexity Hardness The motion-planning-through-gadgets framework has enabled proofs of PSPACE-completeness for many motion-planning problems, ranging from swarm and modular robotics to DNA computing to video games. In this paper, we strengthen this framework to show that, for several useful gadgets and gadget families, motion planning remains PSPACE-complete even when gadgets are connected together into a graph of constant bandwidth (which implies constant pathwidth, treewidth, and cliquewidth). We then show how this result applies to several geometric/grid-based motion-planning problems, establishing PSPACE-completeness even when restricted to a rectangle/box where only one dimension is large (superconstant). On the positive side, we find one family of gadgets (DAG gadgets) for which motion planning is fixed-parameter tractable with respect to bandwidth. Schloss Dagstuhl – Leibniz-Zentrum für Informatik MIT Gadgets Group and Erik D. Demaine and Jenny Diomidova and Timothy Gomez and Markus Hecher and Jayson Lynch 2025 Is Part Of LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2025.11 urn:nbn:de:0030-drops-230648 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode