2026-08-09T18:03:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16999 2024-03-06T10:58:56Z ddc:004 open_access

Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited Gima, Tatsuya Ito, Takehiro Kobayashi, Yasuaki Otachi, Yota Combinatorial reconfiguration monadic second-order logic fixed-parameter tractability treedepth neighborhood diversity Given a graph and two vertex sets satisfying a certain feasibility condition, a reconfiguration problem asks whether we can reach one vertex set from the other by repeating prescribed modification steps while maintaining feasibility. In this setting, Mouawad et al. [IPEC 2014] presented an algorithmic meta-theorem for reconfiguration problems that says if the feasibility can be expressed in monadic second-order logic (MSO), then the problem is fixed-parameter tractable parameterized by treewidth + 𝓁, where 𝓁 is the number of steps allowed to reach the target set. On the other hand, it is shown by Wrochna [J. Comput. Syst. Sci. 2018] that if 𝓁 is not part of the parameter, then the problem is PSPACE-complete even on graphs of bounded bandwidth. In this paper, we present the first algorithmic meta-theorems for the case where 𝓁 is not part of the parameter, using some structural graph parameters incomparable with bandwidth. We show that if the feasibility is defined in MSO, then the reconfiguration problem under the so-called token jumping rule is fixed-parameter tractable parameterized by neighborhood diversity. We also show that the problem is fixed-parameter tractable parameterized by treedepth + k, where k is the size of sets being transformed. We finally complement the positive result for treedepth by showing that the problem is PSPACE-complete on forests of depth 3. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatsuya Gima and Takehiro Ito and Yasuaki Kobayashi and Yota Otachi 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.61 urn:nbn:de:0030-drops-169991 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.61 eng https://creativecommons.org/licenses/by/4.0/legalcode