Basis sequence reconfiguration in the union of matroids
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929498627244032 |
|---|---|
| author | Hanaka, Tesshu Iwamasa, Yuni Kobayashi, Yasuaki Okada, Yuto Saito, Rin |
| author_facet | Hanaka, Tesshu Iwamasa, Yuni Kobayashi, Yasuaki Okada, Yuto Saito, Rin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07848 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Basis sequence reconfiguration in the union of matroids Hanaka, Tesshu Iwamasa, Yuni Kobayashi, Yasuaki Okada, Yuto Saito, Rin Combinatorics Discrete Mathematics 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. |
| title | Basis sequence reconfiguration in the union of matroids |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2409.07848 |