Paper by Erik D. Demaine
- 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.
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
- The paper is 7 pages.
- The paper is available in PDF (334k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated November 6, 2023 by