Search Results

Documents authored by Yamaguchi, Yutaro

Artifact
Software
DOI: 10.4230/artifacts.23553
Code for finding a non-SIBO matroid

Authors: Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi

Abstract
Cite as

Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, Yutaro Yamaguchi. Code for finding a non-SIBO matroid (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23553,
   title = {{Code for finding a non-SIBO matroid}}, 
   author = {Garamv\"{o}lgyi, D\'{a}niel and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s and Yamaguchi, Yutaro},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:ce3aedc8d6702824b0aaf570f3b345e2e24776c1;origin=https://github.com/taiheioki/sibo;visit=swh:1:snp:b12612e562c84d3ca5eb46a9baf151c8e2e2d3a5;anchor=swh:1:rev:79cbfd0a9fbdac083ee3d99fcf40ea4efd878bf8}{\texttt{swh:1:dir:ce3aedc8d6702824b0aaf570f3b345e2e24776c1}} (visited on 2025-06-30)},
   url = {https://github.com/taiheioki/sibo},
   doi = {10.4230/artifacts.23553},
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.85
Towards the Proximity Conjecture on Group-Labeled Matroids

Authors: Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Consider a matroid M whose ground set is equipped with a labeling to an abelian group. A basis of M is called F-avoiding if the sum of the labels of its elements is not in a forbidden label set F. Hörsch, Imolay, Mizutani, Oki, and Schwarcz (2024) conjectured that if an F-avoiding basis exists, then any basis can be transformed into an F-avoiding basis by exchanging at most |F| elements. This proximity conjecture is known to hold for certain specific groups; in the case where |F| ≤ 2; or when the matroid is subsequence-interchangeably base orderable (SIBO), which is a weakening of the so-called strongly base orderable (SBO) property. In this paper, we settle the proximity conjecture for sparse paving matroids or in the case where |F| ≤ 4. Related to the latter result, we present the first known example of a non-SIBO matroid. We further address the setting of multiple group-label constraints, showing proximity results for the cases of two labelings, SIBO matroids, matroids representable over a fixed, finite field, and sparse paving matroids.
Cite as

Dániel Garamvölgyi, Ryuhei Mizutani, Taihei Oki, Tamás Schwarcz, and Yutaro Yamaguchi. Towards the Proximity Conjecture on Group-Labeled Matroids. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 85:1-85:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{garamvolgyi_et_al:LIPIcs.ICALP.2025.85,
  author =	{Garamv\"{o}lgyi, D\'{a}niel and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s and Yamaguchi, Yutaro},
  title =	{{Towards the Proximity Conjecture on Group-Labeled Matroids}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{85:1--85:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.85},
  URN =		{urn:nbn:de:0030-drops-234628},
  doi =		{10.4230/LIPIcs.ICALP.2025.85},
  annote =	{Keywords: sparse paving matroid, subsequence-interchangeable base orderability, congruency constraint, multiple labelings}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.63
Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity

Authors: Yutaro Yamaguchi

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Mader's disjoint S-paths problem unifies two generalizations of bipartite matching: (a) non-bipartite matching and (b) disjoint s–t paths. Lovász (1980, 1981) first proposed an efficient algorithm for this problem via a reduction to matroid matching, which also unifies two generalizations of bipartite matching: (a) non-bipartite matching and (c) matroid intersection. While the weighted versions of the problems (a)-(c) in which we aim to minimize the total weight of a designated-size feasible solution are known to be solvable in polynomial time, the tractability of such a weighted version of Mader's problem has been open for a long while. In this paper, we present the first solution to this problem with the aid of a linear representation for Lovász' reduction (which leads to a reduction to linear matroid parity) due to Schrijver (2003) and polynomial-time algorithms for a weighted version of linear matroid parity announced by Iwata (2013) and by Pap (2013). Specifically, we give a reduction of the weighted version of Mader's problem to weighted linear matroid parity, which leads to an O(n^5)-time algorithm for the former problem, where n denotes the number of vertices in the input graph. Our reduction technique is also applicable to a further generalized framework, packing non-zero A-paths in group-labeled graphs, introduced by Chudnovsky, Geelen, Gerards, Goddyn, Lohman, and Seymour (2006). The extension leads to the tractability of a broader class of weighted problems not restricted to Mader’s setting.
Cite as

Yutaro Yamaguchi. Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 63:1-63:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yamaguchi:LIPIcs.ISAAC.2016.63,
  author =	{Yamaguchi, Yutaro},
  title =	{{Shortest Disjoint S-Paths Via Weighted Linear Matroid Parity}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{63:1--63:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.63},
  URN =		{urn:nbn:de:0030-drops-68325},
  doi =		{10.4230/LIPIcs.ISAAC.2016.63},
  annote =	{Keywords: Mader's S-paths, packing non-zero A-paths in group-labeled graphs, linear matroid parity, weighted problems, tractability}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact