Abstract
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.
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.
Original language | English |
---|---|
Title of host publication | 37th AAAI Conference on Artificial Intelligence, AAAI 2023 |
Pages | 6313-6321 |
Number of pages | 9 |
DOIs | |
Publication status | Published - 26 Jun 2023 |
Event | 37th AAAI Conference on Artificial Intelligence - Washington, United States Duration: 7 Feb 2023 → 14 Feb 2023 https://aaai-23.aaai.org/ |
Conference
Conference | 37th AAAI Conference on Artificial Intelligence |
---|---|
Abbreviated title | AAAI-23 |
Country/Territory | United States |
City | Washington |
Period | 7/02/23 → 14/02/23 |
Internet address |