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.

研究了同步动态系统中的三个问题：系统从初始配置是否过渡到目标配置，系统从初始配置是否达到收敛，以及系统是否保证从所有可能的初始配置达到收敛，通过利用更细粒度的参数化复杂性范式，研究了网络的结构参数的确切可解性边界。对于常数树宽的实例，表明所有三个问题仍然是难解的，但通过参数化为树深度的固定参数算法，对前两个问题提出了补充方案。当参数化为树深度和最大入度时，提出了解决最后一个问题的固定参数算法。

同步动态系统的结构复杂性分析