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. 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
4. New Algorithms and Lower Bounds for Streaming Tournaments

   https://doi.org/10.4230/LIPIcs.ESA.2024.60  

   Ghosh, Prantar ; Kuchlous, Sahil ( January 2024 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Chan, Timothy ; Fischer, Johannes ; Iacono, John ; Herman, Grzegorz (Ed.)

   We study fundamental directed graph (digraph) problems in the streaming model. An initial investigation by Chakrabarti, Ghosh, McGregor, and Vorotnikova [SODA'20] on streaming digraphs showed that while most of these problems are provably hard in general, some of them become tractable when restricted to the well-studied class of tournament graphs where every pair of nodes shares exactly one directed edge. Thus, we focus on tournaments and improve the state of the art for multiple problems in terms of both upper and lower bounds. Our primary upper bound is a deterministic single-pass semi-streaming algorithm (using Õ(n) space for n-node graphs, where Õ(.) hides polylog(n) factors) for decomposing a tournament into strongly connected components (SCC). It improves upon the previously best-known algorithm by Baweja, Jia, and Woodruff [ITCS'22] in terms of both space and passes: for p ⩾ 1, they used (p+1) passes and Õ(n^{1+1/p}) space. We further extend our algorithm to digraphs that are close to tournaments and establish tight bounds demonstrating that the problem’s complexity grows smoothly with the "distance" from tournaments. Applying our SCC-decomposition framework, we obtain improved - and in some cases, optimal - tournament algorithms for s,t-reachability, strong connectivity, Hamiltonian paths and cycles, and feedback arc set. On the other hand, we prove lower bounds exhibiting that some well-studied problems - such as (exact) feedback arc set and s,t-distance - remain hard (require Ω(n²) space) on tournaments. Moreover, we generalize the former problem’s lower bound to establish space-approximation tradeoffs: any single-pass (1± ε)-approximation algorithm requires Ω(n/√{ε}) space. Finally, we settle the streaming complexities of two basic digraph problems studied by prior work: acyclicity testing of tournaments and sink finding in DAGs. As a whole, our collection of results contributes significantly to the growing literature on streaming digraphs. 

   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