Basis Sequence Reconfiguration in the Union of Matroids

Given a graph G and two spanning trees T and T^′ in G, Spanning 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 clog n for some constant c > 0, where n is the total size of the ground sets of the input matroids.