Paper by Erik D. Demaine

Reference:

Hayashi Ani, Erik D. Demaine, Jenny Diomidova, Della Hendrickson, and Jayson Lynch, “Traversability, Reconfiguration, and Reachability in the Gadget Framework”, Algorithmica, volume 85, number 11, 2023, pages 3453–3486.

Abstract:

Consider an agent traversing a graph of “gadgets”, where each gadget has local state that changes with each traversal by the agent according to specified rules. Prior work has studied the computational complexity of deciding whether the agent can reach a specified location, a problem we call reachability. This paper introduces new goals for the agent, aiming to characterize when the computational complexity of these problems is the same or differs from that of reachability. First we characterize the complexity of universal traversal—where the goal is to traverse every gadget at least once—for DAG gadgets (partially), one-state gadgets, and reversible deterministic gadgets. Then we study the complexity of reconfiguration—where the goal is to bring the system of gadgets to a specified state. We prove many cases PSPACE-complete, and show in some cases that reconfiguration is strictly harder than reachability, while in other cases, reachability is strictly harder than reconfiguration.

Comments:

This paper is also available as arXiv:2204.00600 and from SpringerLink.

Availability:

The paper is available in PDF (699k).

See information on file formats.

[Google Scholar search]

Related papers:

GadgetsVictory_WALCOM2022 (Traversability, Reconfiguration, and Reachability in the Gadget Framework)