Paper by Erik D. Demaine

Reference:

Robert M. Alaniz, Michael Coulombe, Erik D. Demaine, Bin Fu, Timothy Gomez, Elise Grizzell, Ryan Knobel, Andrew Rodriguez, Robert Schweller, and Tim Wylie, “Reconfiguration of Linear Surface Chemical Reaction Networks with Bounded State Change”, in Proceedings of the 35th Canadian Conference on Computational Geometry (CCCG 2023), July 31–August 4, 2023, pages 51–61.

Abstract:

We present results on the complexity of reconfiguration of surface Chemical Reaction Networks (sCRNs) in a model where surface vertices can change state a bounded number of times based on a given burnout parameter k. We primarily focus on linear 1 × n surfaces. Without a burnout bound, or even with an exponentially high bound on burnout, reconfiguration on linear surfaces is known to be PSPACE-complete. In contrast, we show that the problem becomes NP-complete when the burnout k is polynomially bounded in n. For smaller k = O(1), we show the problem is polynomial-time solvable, and in the special case of k = 1 burnout, reconfiguration can be solved in linear O(n + |R|) time, where |R| denotes the number of system rules. We additionally explore some extensions of this problem to more general graphs, including a fixed-parameter tractable algorithm in the height m of an m × n rectangle in 1-burnout, a polynomial-time solution for 1-burnout in general graphs if reactions are non-catalytic, and an NP-complete result for 1-burnout in general graphs.

Length:

The paper is 7 pages.

Availability:

The paper is available in PDF (334k).

See information on file formats.

[Google Scholar search]