Search Results

Documents authored by Mizutani, Ryuhei

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.86
Problems on Group-Labeled Matroid Bases

Authors: Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Consider a matroid equipped with a labeling of its ground set to an abelian group. We define the label of a subset of the ground set as the sum of the labels of its elements. We study a collection of problems on finding bases and common bases of matroids with restrictions on their labels. For zero bases and zero common bases, the results are mostly negative. While finding a non-zero basis of a matroid is not difficult, it turns out that the complexity of finding a non-zero common basis depends on the group. Namely, we show that the problem is hard for a fixed group if it contains an element of order two, otherwise it is polynomially solvable. As a generalization of both zero and non-zero constraints, we further study F-avoiding constraints where we seek a basis or common basis whose label is not in a given set F of forbidden labels. Using algebraic techniques, we give a randomized algorithm for finding an F-avoiding common basis of two matroids represented over the same field for finite groups given as operation tables. The study of F-avoiding bases with groups given as oracles leads to a conjecture stating that whenever an F-avoiding basis exists, an F-avoiding basis can be obtained from an arbitrary basis by exchanging at most |F| elements. We prove the conjecture for the special cases when |F| ≤ 2 or the group is ordered. By relying on structural observations on matroids representable over fixed, finite fields, we verify a relaxed version of the conjecture for these matroids. As a consequence, we obtain a polynomial-time algorithm in these special cases for finding an F-avoiding basis when |F| is fixed.
Cite as

Florian Hörsch, András Imolay, Ryuhei Mizutani, Taihei Oki, and Tamás Schwarcz. Problems on Group-Labeled Matroid Bases. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 86:1-86:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{horsch_et_al:LIPIcs.ICALP.2024.86,
  author =	{H\"{o}rsch, Florian and Imolay, Andr\'{a}s and Mizutani, Ryuhei and Oki, Taihei and Schwarcz, Tam\'{a}s},
  title =	{{Problems on Group-Labeled Matroid Bases}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{86:1--86:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.86},
  URN =		{urn:nbn:de:0030-drops-202299},
  doi =		{10.4230/LIPIcs.ICALP.2024.86},
  annote =	{Keywords: matroids, matroid intersection, congruency constraint, exact-weight constraint, additive combinatorics, algebraic algorithm, strongly base orderability}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.46
Minimum 0-Extension Problems on Directed Metrics

Authors: Hiroshi Hirai and Ryuhei Mizutani

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
For a metric μ on a finite set T, the minimum 0-extension problem 0-Ext[μ] is defined as follows: Given V ⊇ T and c:(V 2) → ℚ+, minimize ∑ c(xy)μ(γ(x),γ(y)) subject to γ:V → T, γ(t) = t (∀ t ∈ T), where the sum is taken over all unordered pairs in V. This problem generalizes several classical combinatorial optimization problems such as the minimum cut problem or the multiterminal cut problem. The complexity dichotomy of 0-Ext[μ] was established by Karzanov and Hirai, which is viewed as a manifestation of the dichotomy theorem for finite-valued CSPs due to Thapper and Živný. In this paper, we consider a directed version 0→-Ext[μ] of the minimum 0-extension problem, where μ and c are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext[μ] to 0→-Ext[μ]: If μ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant "directed" edge-length, then 0→-Ext[μ] is NP-hard. We also show a partial converse: If μ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then 0→-Ext[μ] is tractable. We further provide a new NP-hardness condition characteristic of 0→-Ext[μ], and establish a dichotomy for the case where μ is a directed metric of a star.
Cite as

Hiroshi Hirai and Ryuhei Mizutani. Minimum 0-Extension Problems on Directed Metrics. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hirai_et_al:LIPIcs.MFCS.2020.46,
  author =	{Hirai, Hiroshi and Mizutani, Ryuhei},
  title =	{{Minimum 0-Extension Problems on Directed Metrics}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.46},
  URN =		{urn:nbn:de:0030-drops-127120},
  doi =		{10.4230/LIPIcs.MFCS.2020.46},
  annote =	{Keywords: Minimum 0-extension problems, Directed metrics, Valued constraint satisfaction problems, Computational complexity}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact