A Structural Complexity Analysis of Synchronous Dynamical Systems
Authors: Eduard Eiben, Robert Ganian, Thekla Hamm, Viktoriia Korchemna
AAAI 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | 1 Department of Computer Science, Royal Holloway, University of London, UK 2 Algorithms and Complexity Group, TU Wien, Austria 3 Utrecht University, Netherlands |
| Pseudocode | No | The paper describes algorithms conceptually but does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not mention the use of datasets for training or provide access information for any public dataset. |
| Dataset Splits | No | The paper is theoretical and does not mention training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not provide specific hardware details used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not provide specific experimental setup details like hyperparameters or training configurations. |