Paper by Erik D. Demaine

Joshua Ani, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch, “Traversability, Reconfiguration, and Reachability in the Gadget Framework”, in Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), edited by Petra Mutzel, Md. Saidur Rahman, and Slamin, Lecture Notes in Computer Science, volume 13174, Jember, Indonesia, March 2022, pages 47–58.

Consider an agent traversing a graph of “gadgets”, each with local state that changes with each traversal by the agent. Prior work has studied the computational complexity of deciding whether the agent can reach a target location given a graph containing many copies of a given type of gadget. This paper introduces new goals and studies examples where the computational complexity of these problems are the same or differ from the original relocation goal. For several classes of gadgets—DAG gadgets, one-state gadgets, and reversible deterministic gadgets—we give a partial characterization of their complexity when the goal is to traverse every gadget at least once. We also study the complexity of reconfiguration, where the goal is to bring the entire system of gadgets to a specified state. We give examples where reconfiguration is a strictly harder problem than relocating the agent, and also examples where relocation is strictly harder. We also give a partial characterization of the complexity of reconfiguration with reversible deterministic gadgets.

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

The paper is available in PDF (412k).
See information on file formats.
[Google Scholar search]

Related papers:
GadgetsVictory_Algorithmica (Traversability, Reconfiguration, and Reachability in the Gadget Framework)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 12, 2024 by Erik Demaine.