2026-09-21T03:35:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26039 2026-09-05T19:35:17Z ddc:004 open_access

Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks Bajaj, Divya Fu, Bin Knobel, Ryan Luchsinger, Austin Massie, Aiden Santos, Pablo Santos, Ramiro Schweller, Robert Tomai, Evan Wylie, Tim Chemical Reaction Networks Vector Addition Systems Petri-nets Reachability Inhibitors Void Reactions Chemical Reaction Networks (CRNs) are a well-established model of distributed computing characterized by quantities of molecular species that can transform or change through applications of reactions. A fundamental problem in CRNs is the reachability problem, which asks if an initial configuration of species can transition to a target configuration through an applicable sequence of reactions. It is well-known that the reachability problem in general CRNs was recently proven to be Ackermann-complete. However, if the CRN’s reactions are restricted in both power, such as only deleting species (deletion-only rules) or consuming and producing an equal number of species (volume-preserving rules), and size (unimolecular or bimolecular rules), then reachability falls below Ackermann-completeness, and is even solvable in polynomial time for deletion-only systems. In this paper, we investigate reachability under this set of restricted unimolecular and bimolecular reactions, but in the Priority-Inhibitory CRN and Inhibitory CRN models. These models extend a traditional CRN by allowing some reactions to be inhibited from firing in a configuration if certain species are present; the exact inhibition behavior varies between the models. We first show that reachability with Priority iCRNs mostly remains in P for deletion-only systems, but becomes NP-complete for one case. We then show that reachability with deletion-only reactions for iCRNs is mostly NP-complete, and PSPACE-complete even for (1,1)-size (general) reactions. We also provide FPT algorithms for solving most of the reachability problems for the iCRN model. Finally, we show reachability for CRNs with states is already NP-hard for the simplest deletion-only systems, and is PSPACE-complete even for (general) (1,1)-size reactions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Divya Bajaj and Bin Fu and Ryan Knobel and Austin Luchsinger and Aiden Massie and Pablo Santos and Ramiro Santos and Robert Schweller and Evan Tomai and Tim Wylie 2026 Is Part Of LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2026.3 urn:nbn:de:0030-drops-260399 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.3 eng https://creativecommons.org/licenses/by/4.0/legalcode