License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.46
URN: urn:nbn:de:0030-drops-127120
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12712/
Go to the corresponding LIPIcs Volume Portal

Hirai, Hiroshi ; Mizutani, Ryuhei

Minimum 0-Extension Problems on Directed Metrics

pdf-format:
LIPIcs-MFCS-2020-46.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{hirai_et_al:LIPIcs:2020:12712,
  author =	{Hiroshi Hirai and Ryuhei Mizutani},
  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 =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12712},
  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}
}

Keywords: Minimum 0-extension problems, Directed metrics, Valued constraint satisfaction problems, Computational complexity
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI