DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.38

Basis Sequence Reconfiguration in the Union of Matroids

Authors: Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi, Yuto Okada, and Rin Saito

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

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.

Cite as

Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi, Yuto Okada, and Rin Saito. Basis Sequence Reconfiguration in the Union of Matroids. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hanaka_et_al:LIPIcs.ISAAC.2024.38,
  author =	{Hanaka, Tesshu and Iwamasa, Yuni and Kobayashi, Yasuaki and Okada, Yuto and Saito, Rin},
  title =	{{Basis Sequence Reconfiguration in the Union of Matroids}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.38},
  URN =		{urn:nbn:de:0030-drops-221658},
  doi =		{10.4230/LIPIcs.ISAAC.2024.38},
  annote =	{Keywords: Combinatorial reconfiguration, Matroids, Polynomial-time algorithm, Inapproximability}
}

Search Results

Documents authored by Saito, Rin

Basis Sequence Reconfiguration in the Union of Matroids

Abstract

Cite as

Thanks for your feedback!

Could not send message