Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms
Keywords:Other Foundations of Multi Agent Systems
AbstractDiscrete 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.
How to Cite
Rosenkrantz, D. J., Marathe, M., Ravi, S. S., & Stearns, R. E. (2021). Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms. Proceedings of the AAAI Conference on Artificial Intelligence, 35(13), 11334-11342. https://doi.org/10.1609/aaai.v35i13.17351
AAAI Technical Track on Multiagent Systems