2026-07-25T01:58:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22165 2024-12-04T06:53:44Z ddc:004 open_access

Basis Sequence Reconfiguration in the Union of Matroids Hanaka, Tesshu Iwamasa, Yuni Kobayashi, Yasuaki Okada, Yuto Saito, Rin Combinatorial reconfiguration Matroids Polynomial-time algorithm Inapproximability Given a graph G and two spanning trees T and T' in G, normalSpanning Tree Reconfiguration asks whether there is a step-by-step transformation from T to T' such that all intermediates are also spanning trees of G, by exchanging an edge in T with an edge outside T at a single step. This problem is naturally related to matroid theory, which shows that there always exists such a transformation for any pair of T and T'. Motivated by this example, we study the problem of transforming a sequence of spanning trees into another sequence of spanning trees. We formulate this problem in the language of matroid theory: Given two sequences of bases of matroids, the goal is to decide whether there is a transformation between these sequences. We design a polynomial-time algorithm for this problem, even if the matroids are given as basis oracles. To complement this algorithmic result, we show that the problem of finding a shortest transformation is NP-hard to approximate within a factor of c log n for some constant c > 0, where n is the total size of the ground sets of the input matroids. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tesshu Hanaka and Yuni Iwamasa and Yasuaki Kobayashi and Yuto Okada and Rin Saito 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.38 urn:nbn:de:0030-drops-221658 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.38 eng https://creativecommons.org/licenses/by/4.0/legalcode