A Structural Complexity Analysis of Synchronous Dynamical Systems
This work addresses fundamental computational challenges in network modeling for researchers in theoretical computer science and complex systems, offering incremental algorithmic improvements.
The paper tackled the intractability of three key problems in synchronous dynamical systems by analyzing them through structural parameters like treewidth and treedepth, showing that all three remain intractable even with constant treewidth but providing fixed-parameter algorithms for two problems with treedepth and one with treedepth plus maximum in-degree.
Synchronous dynamic systems are well-established models that have been used to capture a range of phenomena in networks, including opinion diffusion, spread of disease and product adoption. We study the three most notable problems in synchronous dynamic systems: whether the system will transition to a target configuration from a starting configuration, whether the system will reach convergence from a starting configuration, and whether the system is guaranteed to converge from every possible starting configuration. While all three problems were known to be intractable in the classical sense, we initiate the study of their exact boundaries of tractability from the perspective of structural parameters of the network by making use of the more fine-grained parameterized complexity paradigm. As our first result, we consider treewidth - as the most prominent and ubiquitous structural parameter - and show that all three problems remain intractable even on instances of constant treewidth. We complement this negative finding with fixed-parameter algorithms for the former two problems parameterized by treedepth, a well-studied restriction of treewidth. While it is possible to rule out a similar algorithm for convergence guarantee under treedepth, we conclude with a fixed-parameter algorithm for this last problem when parameterized by treedepth and the maximum in-degree.