Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms
Synchronous Dynamical Systems on Directed Acyclic Graphs: Complexity and Algorithms
复制标题
DOI：
10.1145/3653723
复制
发表时间：
2021-05
影响因子：
0.7
通讯作者：
D. Rosenkrantz;M. Marathe;S. Ravi;R. Stearns
中科院分区：
文献类型：
--
作者：
D. Rosenkrantz;M. Marathe;S. Ravi;R. Stearns
离散动力系统是研究社会网络中扩散现象的有效形式模型。最近有几篇文章研究了同步布尔网络上一些决策问题的算法和复杂性方面。同步布尔网络是离散动态系统，其底层图是有向的，并且可能包含有向循环。这类问题可以看作是相应动力系统相空间中的可达性问题。先前的研究表明，对于有向无环图（dag）上的系统，其中一些决策问题可以有效地求解。在此工作的激励下，我们研究了一些底层图为dag的动态系统的决策问题。我们证明了可达性问题的计算难解性（即pspace完备性）结果甚至适用于dag上的动态系统。我们还发现了一些动态系统在dag上的限制版本，它们可以有效地解决可达性问题。此外，我们还证明了一个决策问题（即收敛问题）对于dag上的动态系统是有效可解的，对于拟dag（即，通过去除单个边而成为dag的图）来说是pspace完全的。在建立上述结果的过程中，我们还开发了dag上动力系统相空间的几个结构性质。
Discrete dynamical systems serve as useful formal models to study diffusion phenomena in social networks. Several recent articles have studied the algorithmic and complexity aspects of some decision problems on synchronous Boolean networks, which are discrete 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. Previous work has shown that some of these decision problems become efficiently solvable for systems on directed acyclic graphs (DAGs). Motivated by this line of work, we investigate a number of decision problems for dynamical systems whose underlying graphs are DAGs. We show that computational intractability (i.e., PSPACE-completeness) results for reachability problems hold even for dynamical systems on DAGs. We also identify some restricted versions of dynamical systems on DAGs for which reachability problem can be solved efficiently. In addition, we show that a decision problem (namely, Convergence), which is efficiently solvable for dynamical systems on DAGs, becomes PSPACE-complete for Quasi-DAGs (i.e., graphs that become DAGs by the removal of a single edge). In the process of establishing the above results, we also develop several structural properties of the phase spaces of dynamical systems on DAGs.