6 Search Results for "Hirai, Hiroshi"

Document
DOI: 10.4230/LIPIcs.ISAAC.2021.18
Interval Query Problem on Cube-Free Median Graphs

Authors: Soh Kumabe

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In this paper, we introduce the interval query problem on cube-free median graphs. Let G be a cube-free median graph and 𝒮 be a commutative semigroup. For each vertex v in G, we are given an element p(v) in 𝒮. For each query, we are given two vertices u,v in G and asked to calculate the sum of p(z) over all vertices z belonging to a u-v shortest path. This is a common generalization of range query problems on trees and grids. In this paper, we provide an algorithm to answer each interval query in O(log² n) time. The required data structure is constructed in O(n log³ n) time and O(n log² n) space. To obtain our algorithm, we introduce a new technique, named the staircases decomposition, to decompose an interval of cube-free median graphs into simpler substructures.
Cite as

Soh Kumabe. Interval Query Problem on Cube-Free Median Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kumabe:LIPIcs.ISAAC.2021.18,
  author =	{Kumabe, Soh},
  title =	{{Interval Query Problem on Cube-Free Median Graphs}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.18},
  URN =		{urn:nbn:de:0030-drops-154510},
  doi =		{10.4230/LIPIcs.ISAAC.2021.18},
  annote =	{Keywords: Data Structures, Range Query Problems, Median Graphs}
}
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-dev.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}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.65
Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity

Authors: Hiroshi Hirai and Motoki Ikeda

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The terminal backup problems [Anshelevich and Karagiozova, 2011] form a class of network design problems: Given an undirected graph with a requirement on terminals, the goal is to find a minimum cost subgraph satisfying the connectivity requirement. The node-connectivity terminal backup problem requires a terminal to connect other terminals with a number of node-disjoint paths. This problem is not known whether is NP-hard or tractable. Fukunaga (2016) gave a 4/3-approximation algorithm based on LP-rounding scheme using a general LP-solver. In this paper, we develop a combinatorial algorithm for the relaxed LP to find a half-integral optimal solution in O(mlog (mUA)⋅ MF(kn,m+k²n)) time, where m is the number of edges, k is the number of terminals, A is the maximum edge-cost, U is the maximum edge-capacity, and MF(n',m') is the time complexity of a max-flow algorithm in a network with n' nodes and m' edges. The algorithm implies that the 4/3-approximation algorithm for the node-connectivity terminal backup problem is also efficiently implemented. For the design of algorithm, we explore a connection between the node-connectivity terminal backup problem and a new type of a multiflow, called a separately-capacitated multiflow. We show a min-max theorem which extends Lovász - Cherkassky theorem to the node-capacity setting. Our results build on discrete convex analysis for the node-connectivity terminal backup problem.
Cite as

Hiroshi Hirai and Motoki Ikeda. Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 65:1-65:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hirai_et_al:LIPIcs.ICALP.2020.65,
  author =	{Hirai, Hiroshi and Ikeda, Motoki},
  title =	{{Node-Connectivity Terminal Backup, Separately-Capacitated Multiflow, and Discrete Convexity}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{65:1--65:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.65},
  URN =		{urn:nbn:de:0030-drops-124725},
  doi =		{10.4230/LIPIcs.ICALP.2020.65},
  annote =	{Keywords: terminal backup problem, node-connectivity, separately-capacitated multiflow, discrete convex analysis}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.89
On Solving (Non)commutative Weighted Edmonds' Problem

Authors: Taihei Oki

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper, we consider computing the degree of the Dieudonné determinant of a polynomial matrix A = A_l + A_{l-1} s + ⋯ + A₀ s^l, where each A_d is a linear symbolic matrix, i.e., entries of A_d are affine functions in symbols x₁, …, x_m over a field K. This problem is a natural "weighted analog" of Edmonds' problem, which is to compute the rank of a linear symbolic matrix. Regarding x₁, …, x_m as commutative or noncommutative, two different versions of weighted and unweighted Edmonds' problems can be considered. Deterministic polynomial-time algorithms are unknown for commutative Edmonds' problem and have been proposed recently for noncommutative Edmonds' problem. The main contribution of this paper is to establish a deterministic polynomial-time reduction from (non)commutative weighted Edmonds' problem to unweighed Edmonds' problem. Our reduction makes use of the discrete Legendre conjugacy between the integer sequences of the maximum degree of minors of A and the rank of linear symbolic matrices obtained from the coefficient matrices of A. Combined with algorithms for noncommutative Edmonds' problem, our reduction yields the first deterministic polynomial-time algorithm for noncommutative weighted Edmonds' problem with polynomial bit-length bounds. We also give a reduction of the degree computation of quasideterminants and its application to the degree computation of noncommutative rational functions.
Cite as

Taihei Oki. On Solving (Non)commutative Weighted Edmonds' Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 89:1-89:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{oki:LIPIcs.ICALP.2020.89,
  author =	{Oki, Taihei},
  title =	{{On Solving (Non)commutative Weighted Edmonds' Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{89:1--89:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.89},
  URN =		{urn:nbn:de:0030-drops-124963},
  doi =		{10.4230/LIPIcs.ICALP.2020.89},
  annote =	{Keywords: skew fields, Edmonds' problem, Dieudonn\'{e} determinant, degree computation, Smith - McMillan form, matrix expansion, discrete Legendre conjugacy}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.57
Reconstructing Phylogenetic Tree From Multipartite Quartet System

Authors: Hiroshi Hirai and Yuni Iwamasa

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
A phylogenetic tree is a graphical representation of an evolutionary history in a set of taxa in which the leaves correspond to taxa and the non-leaves correspond to speciations. One of important problems in phylogenetic analysis is to assemble a global phylogenetic tree from smaller pieces of phylogenetic trees, particularly, quartet trees. Quartet Compatibility is to decide whether there is a phylogenetic tree inducing a given collection of quartet trees, and to construct such a phylogenetic tree if it exists. It is known that Quartet Compatibility is NP-hard but there are only a few results known for polynomial-time solvable subclasses. In this paper, we introduce two novel classes of quartet systems, called complete multipartite quartet system and full multipartite quartet system, and present polynomial time algorithms for Quartet Compatibility for these systems. We also see that complete/full multipartite quartet systems naturally arise from a limited situation of block-restricted measurement.
Cite as

Hiroshi Hirai and Yuni Iwamasa. Reconstructing Phylogenetic Tree From Multipartite Quartet System. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 57:1-57:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hirai_et_al:LIPIcs.ISAAC.2018.57,
  author =	{Hirai, Hiroshi and Iwamasa, Yuni},
  title =	{{Reconstructing Phylogenetic Tree From Multipartite Quartet System}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{57:1--57:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.57},
  URN =		{urn:nbn:de:0030-drops-100056},
  doi =		{10.4230/LIPIcs.ISAAC.2018.57},
  annote =	{Keywords: phylogenetic tree, quartet system, reconstruction}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.39
Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection

Authors: Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Zivny

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
A binary VCSP is a general framework for the minimization problem of a function represented as the sum of unary and binary cost functions.An important line of VCSP research is to investigate what functions can be solved in polynomial time. Cooper-Zivny classified the tractability of binary VCSP instances according to the concept of "triangle," and showed that the only interesting tractable case is the one induced by the joint winner property (JWP). Recently, Iwamasa-Murota-Zivny made a link between VCSP and discrete convex analysis, showing that a function satisfying the JWP can be transformed into a function represented as the sum of two M-convex functions, which can be minimized in polynomial time via an M-convex intersection algorithm if the value oracle of each M-convex function is given. In this paper, we give an algorithmic answer to a natural question: What binary finite-valued CSP instances can be solved in polynomial time via an M-convex intersection algorithm? We solve this problem by devising a polynomial-time algorithm for obtaining a concrete form of the representation in the representable case. Our result presents a larger tractable class of binary finite-valued CSPs, which properly contains the JWP class.
Cite as

Hiroshi Hirai, Yuni Iwamasa, Kazuo Murota, and Stanislav Zivny. Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 39:1-39:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hirai_et_al:LIPIcs.STACS.2018.39,
  author =	{Hirai, Hiroshi and Iwamasa, Yuni and Murota, Kazuo and Zivny, Stanislav},
  title =	{{Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.39},
  URN =		{urn:nbn:de:0030-drops-85042},
  doi =		{10.4230/LIPIcs.STACS.2018.39},
  annote =	{Keywords: valued constraint satisfaction problems, discrete convex analysis, M-convexity}
}
  • Refine by Author
  • 4 Hirai, Hiroshi
  • 2 Iwamasa, Yuni
  • 1 Ikeda, Motoki
  • 1 Kumabe, Soh
  • 1 Mizutani, Ryuhei
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Combinatorial algorithms
  • 2 Mathematics of computing → Combinatorial optimization
  • 1 Computing methodologies → Combinatorial algorithms
  • 1 Computing methodologies → Linear algebra algorithms
  • 1 Theory of computation → Algebraic complexity theory

  • Refine by Keyword
  • 2 discrete convex analysis
  • 1 Computational complexity
  • 1 Data Structures
  • 1 Dieudonné determinant
  • 1 Directed metrics
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 3 2020
  • 2 2018
  • 1 2021

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 Imprint Privacy Contact