Minimum 0-extension problems on directed metrics

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: For a metric

m u

on a finite set

T

, the minimum 0-extension problem 0-Ext

[m u]

is defined as follows: Given

V s u p s e t e q T

and

c : V c h o o s e 2 i g h t a r r o w m a t h b f Q_{+}

, minimize

s u m c (x y) m u (g a m m a (x), g a m m a (y))

subject to

g a m m a : V i g h t a r r o w T, g a m m a (t) = t (f o r a l l t i n 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

[m u]

was established by Karzanov and Hirai, which is viewed as a manifestation of the dichotomy theorem for finite-valued CSPs due to Thapper and v{Z}ivn'{y}. In this paper, we consider a directed version

o v e r r i g h t a r r o w 0

-Ext

[m u]

of the minimum 0-extension problem, where

m u

and

c

are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext

[m u]

to

o v e r r i g h t a r r o w 0

-Ext

[m u]

: If

m u

cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed edge-length, then $o v e r r i g h t a r r o w 0$ -Ext $[m u]$ is NP-hard. We also show a partial converse: If $m u$ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then $o v e r r i g h t a r r o w 0$ -Ext $[m u]$ is tractable. We further provide a new NP-hardness condition characteristic of $o v e r r i g h t a r r o w 0$ -Ext $[m u]$ , and establish a dichotomy for the case where $m u$ is a directed metric of a star.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Minimum 0-extension problems on directed metrics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2042078)