Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms
Abstract
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.
Cite
Text
Rosenkrantz et al. "Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I13.17351Markdown
[Rosenkrantz et al. "Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/rosenkrantz2021aaai-synchronous/) doi:10.1609/AAAI.V35I13.17351BibTeX
@inproceedings{rosenkrantz2021aaai-synchronous,
title = {{Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms}},
author = {Rosenkrantz, Daniel J. and Marathe, Madhav V. and Ravi, S. S. and Stearns, Richard Edwin},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2021},
pages = {11334-11342},
doi = {10.1609/AAAI.V35I13.17351},
url = {https://mlanthology.org/aaai/2021/rosenkrantz2021aaai-synchronous/}
}