2026-08-21T16:28:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27437 2026-08-21T14:42:40Z ddc:004 open_access

Lower Bounds for Meta-Reconfiguration Eickmeyer, Kord Gima, Tatsuya Lampis, Michael Mitsou, Valia Nemery, Edouard Otachi, Yota Vasilakis, Manolis Vaz, Daniel Combinatorial Reconfiguration Token Jumping Algorithmic Meta-Theorem Fixed-Parameter Tractability In this paper, we explore the limits of algorithmic meta-theorems for combinatorial reconfiguration on graphs and prove several intractability results for highly restricted cases, which tightly complement the positive results by Mouawad et al. [IPEC 2014] and Gima et al. [Algorithmica 2024]. In this setting, we study reconfiguration problems on graphs in which the feasible sets are defined by formulas of first-order or monadic second-order logic: for a formula φ(X) with a free set variable X, the problem asks whether two given sets are connected by a token-jumping sequence in which every set satisfies φ on the input graph. Our main contribution is to show that the problem is intractable even for first-order logic and for severely restricted graphs, such as paths and disjoint unions of stars or cliques. Combined with known results, these results settle the parameterized complexity for most of the well-studied structural parameters. We also study the setting where the sets to be reconfigured are small, i.e., their size is part of the parameter, and show that even in this setting the problem is hard for caterpillars, whereas it becomes tractable even for monadic second-order logic when parameterized additionally by shrub-depth. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kord Eickmeyer and Tatsuya Gima and Michael Lampis and Valia Mitsou and Edouard Nemery and Yota Otachi and Manolis Vasilakis and Daniel Vaz 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.55 urn:nbn:de:0030-drops-274373 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.55 eng https://creativecommons.org/licenses/by/4.0/legalcode