2026-07-22T18:58:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19428 2024-03-06T11:04:01Z ddc:004 open_access

Minimum Separator Reconfiguration C. M. Gomes, Guilherme Legrand-Duchesne, Clément Mahmoud, Reem Mouawad, Amer E. Okamoto, Yoshio F. dos Santos, Vinicius C. van der Zanden, Tom minimum separators combinatorial reconfiguration parameterized complexity kernelization We study the problem of reconfiguring one minimum s-t-separator A into another minimum s-t-separator B in some n-vertex graph G containing two non-adjacent vertices s and t. We consider several variants of the problem as we focus on both the token sliding and token jumping models. Our first contribution is a polynomial-time algorithm that computes (if one exists) a minimum-length sequence of slides transforming A into B. We additionally establish that the existence of a sequence of jumps (which need not be of minimum length) can be decided in polynomial time (by an algorithm that also outputs a witnessing sequence when one exists). In contrast, and somewhat surprisingly, we show that deciding if a sequence of at most 𝓁 jumps can transform A into B is an NP-complete problem. To complement this negative result, we investigate the parameterized complexity of what we believe to be the two most natural parameterized counterparts of the latter problem; in particular, we study the problem of computing a minimum-length sequence of jumps when parameterized by the size k of the minimum s-t-separators and when parameterized by the number 𝓁 of jumps. For the first parameterization, we show that the problem is fixed-parameter tractable, but does not admit a polynomial kernel unless NP ⊆ coNP/poly. We complete the picture by designing a kernel with 𝒪(𝓁²) vertices and edges for the length 𝓁 of the sequence as a parameter. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Guilherme C. M. Gomes and Clément Legrand-Duchesne and Reem Mahmoud and Amer E. Mouawad and Yoshio Okamoto and Vinicius F. dos Santos and Tom C. van der Zanden 2023 Is Part Of LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2023.9 urn:nbn:de:0030-drops-194288 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode