Basis sequence reconfiguration in the union of matroids
<|reference_start|>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 $c \log n$ for some constant $c > 0$, where $n$ is the total size of the ground sets of the input matroids.<|reference_end|>
@article{hanaka2024basis,
    title={Basis sequence reconfiguration in the union of matroids},
    author={Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi, Yuto Okada, Rin Saito},
    journal={arXiv preprint arXiv:2409.07848},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07848},
    primaryClass={math.CO cs.DM}
}