A Structural Complexity Analysis of Synchronous Dynamical Systems

Eduard Eiben, Robert Ganian, Thekla Hamm, Viktoriia Korchemna

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Downloads (Pure)

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.
Original languageEnglish
Title of host publication37th AAAI Conference on Artificial Intelligence, AAAI 2023
Pages6313-6321
Number of pages9
DOIs
Publication statusPublished - 26 Jun 2023
Event37th AAAI Conference on Artificial Intelligence - Washington, United States
Duration: 7 Feb 202314 Feb 2023
https://aaai-23.aaai.org/

Conference

Conference37th AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI-23
Country/TerritoryUnited States
CityWashington
Period7/02/2314/02/23
Internet address

Cite this