2026-10-19T07:05:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12890 2024-03-06T09:51:00Z ddc:004 open_access

Reconfiguration of Spanning Trees with Many or Few Leaves Bousquet, Nicolas Ito, Takehiro Kobayashi, Yusuke Mizuta, Haruka Ouvrard, Paul Suzuki, Akira Wasa, Kunihiro combinatorial reconfiguration spanning trees PSPACE polynomial-time algorithms Let G be a graph and T₁,T₂ be two spanning trees of G. We say that T₁ can be transformed into T₂ via an edge flip if there exist two edges e ∈ T₁ and f in T₂ such that T₂ = (T₁⧵e) ∪ f. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed in [Takehiro Ito et al., 2011]. We investigate the problem of determining, given two spanning trees T₁,T₂ with an additional property Π, if there exists an edge flip transformation from T₁ to T₂ keeping property Π all along. First we show that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at most k (for any fixed k ≥ 3) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from T₁ to T₂ such that all the trees of the sequence have at least k leaves (where k is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when k = n-2. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bousquet and Takehiro Ito and Yusuke Kobayashi and Haruka Mizuta and Paul Ouvrard and Akira Suzuki and Kunihiro Wasa 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.24 urn:nbn:de:0030-drops-128909 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.24 eng https://creativecommons.org/licenses/by/3.0/legalcode