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”, 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.

Abstract:

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.

Comments:

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

Availability:

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)