1 Search Results for "Mizutani, Ryuhei"

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}
}

Refine by Author
1 Hirai, Hiroshi
1 Mizutani, Ryuhei

Refine by Classification
1 Mathematics of computing → Combinatorial optimization

Refine by Keyword
1 Computational complexity
1 Directed metrics
1 Minimum 0-extension problems
1 Valued constraint satisfaction problems

Refine by Type
1 document

Refine by Publication Year
1 2020

1 Search Results for "Mizutani, Ryuhei"

Minimum 0-Extension Problems on Directed Metrics

Abstract

Cite as

Thanks for your feedback!

Could not send message