More Like this

1. Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms

   Rosenkrantz, Daniel; Marathe, Madhav; Ravi, S.S.; Stearns, Richard (May 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Motivated by applications in systems biology, several recent papers have studied algorithmic and complexity aspects of diffusion problems for dynamical systems whose underlying graphs are directed, and may contain directed cycles. Such problems can be regarded as reachability problems in the phase space of the corresponding dynamical system. We show that computational intractability results for reachability problems hold even for dynamical systems on directed acyclic graphs (dags). We also show that for dynamical systems on dags where each local function is monotone, the reachability problem can be solved efficiently. 

   more » « less
2. Testing phase space properties of synchronous dynamical systems with nested canalyzing local functions.

   Rosenkrantz, D; Marathe, M; Ravi, S; Stearns, R (January 2018, AAMAS 2018)

   Discrete graphical dynamical systems serve as effective formal models in many contexts, including simulations of agent-based models, propagation of contagions in social networks and study of biological phenomena. A class of Boolean functions, called nested canalyzing functions (NCFs), has been used as a good model of certain biological phenomena. Motivated by these biological applications, we study a variety of analysis problems for synchronous graphical dynamical systems (SyDSs) over the Boolean domain, where each local function is an NCF. Each analysis problem involves testing whether the phase space of a given SyDS satisfies a certain property. We present intractability results for some properties as well as efficient algorithms for others. In several cases, our results clearly delineate intractable and efficiently solvable versions of problems 

   more » « less
3. Reachability in Deletion-Only Chemical Reaction Networks

   https://doi.org/10.4230/lipics.dna.31.3  

   Fu, Bin; Gomez, Timothy; Knobel, Ryan; Luchsinger, Austin; Massie, Aiden; Rodriguez, Marco; Salinas, Adrian; Schweller, Robert; Wylie, Tim (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Schaeffer, Josie; Zhang, Fei (Ed.)

   For general discrete Chemical Reaction Networks (CRNs), the fundamental problem of reachability - the question of whether a target configuration can be produced from a given initial configuration - was recently shown to be Ackermann-complete. However, many open questions remain about which features of the CRN model drive this complexity. We study a restricted class of CRNs with void rules, reactions that only decrease species counts. We further examine this regime in the motivated model of step CRNs, which allow additional species to be introduced in discrete stages. With and without steps, we characterize the complexity of the reachability problem for CRNs with void rules. We show that, without steps, reachability remains polynomial-time solvable for bimolecular systems but becomes NP-complete for larger reactions. Conversely, with just a single step, reachability becomes NP-complete even for bimolecular systems. Our results provide a nearly complete classification of void-rule reachability problems into tractable and intractable cases, with only a single exception. 

   more » « less
4. Realization Problems on Reachability Sequences

   Dippel, Matthew; Sundaram, Ravi; Varma, Akshar (January 2020, COCOON)

   The classical Erdös-Gallai theorem kicked off the study ofgraph realizability by characterizing degree sequences. We extend this line of research by investigating realizability of directed acyclic graphs (DAGs)given both a local constraint via degree sequences and a global constraint via a sequence of reachability values (number of nodes reachable from a given node). We show that, without degree constraints, DAG reachability realization is solvable in linear time, whereas it is strongly NP-complete given upper bounds on in-degree or out-degree. After defining a suitable notion of bicriteria approximation based on consistency, we give two approximation algorithms achieving O(logn)-reachability consistency and O(logn)-degree consistency; the first, randomized, uses LP (Linear Program) rounding, while the second, deterministic, employs ak-setpacking heuristic. We end with two conjectures that we hope motivate further study of realizability with reachability constraints. 

   more » « less
5. Computing and optimizing over all fixed-points of discrete systems on large networks

   https://doi.org/10.1098/rsif.2020.0126  

   Riehl, James R.; Zimmerman, Maxwell I.; Singh, Matthew F.; Bowman, Gregory R.; Ching, ShiNung (September 2020, Journal of The Royal Society Interface)

   Equilibria, or fixed points, play an important role in dynamical systems across various domains, yet finding them can be computationally challenging. Here, we show how to efficiently compute all equilibrium points of discrete-valued, discrete-time systems on sparse networks. Using graph partitioning, we recursively decompose the original problem into a set of smaller, simpler problems that are easy to compute, and whose solutions combine to yield the full equilibrium set. This makes it possible to find the fixed points of systems on arbitrarily large networks meeting certain criteria. This approach can also be used without computing the full equilibrium set, which may grow very large in some cases. For example, one can use this method to check the existence and total number of equilibria, or to find equilibria that are optimal with respect to a given cost function. We demonstrate the potential capabilities of this approach with examples in two scientific domains: computing the number of fixed points in brain networks and finding the minimal energy conformations of lattice-based protein folding models. 

   more » « less