AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the AAAI Conference on Artificial Intelligence, 35 > No. 13: AAAI-21 Technical Tracks 13

Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms

Authors

Daniel J. Rosenkrantz

Bicomplexity Institute and Initiative, University of Virginia and Computer Science Dept., University at Albany -- SUNY


Madhav Marathe

Biocomplexity Institute & Initiative and Computer Science Dept., University of Virginia


S. S. Ravi

Biocomplexity Institute and Initiative, University of Virginia and Computer Science Dept., University at Albany -- SUNY


Richard E. Stearns

Biocomplexity Institute and Initiative, University of Virginia and Computer Science Dept., University at Albany -- SUNY


Proceedings:

No. 13: AAAI-21 Technical Tracks 13

Volume

Issue:

Proceedings of the AAAI Conference on Artificial Intelligence, 35

Track:

AAAI Technical Track on Multiagent Systems

Downloads:

Download PDF

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.

DOI:

10.1609/aaai.v35i13.17351


AAAI

Proceedings of the AAAI Conference on Artificial Intelligence, 35