论文标题
在指示指标上的最低0延伸问题
Minimum 0-Extension Problems on Directed Metrics
论文作者
论文摘要
对于有限套$ t $的度量$μ$，至少0-延迟问题0- ext $ [μ] $定义如下：给定$ v \ supseteq t $和$ \ c：{v \ select 2} \ rightarrow \ rightarrow \ rightarrow \ mathbf \ mathbf {q _+} $，最小$ \ sum c（ymimize $ c（y）$ c（y）（xy）（xy）（xy）（xy）（xy）（xy）（xy（x）（xy）（xy（x）（xy）（xy（x）（xy（x）（x）（xy（x）（x）（x y°（x）（x Y）。 $γ：v \ rightarrow t，\γ（t）= t \（\ forall t \ in t）$，其中总和在$ v $中以所有无序对。这个问题概括了几个经典的组合优化问题，例如最小切割问题或多局部切割问题。 Karzanov和Hirai建立了一个完全分类的指标$μ$，该指标为0- ext $ [μ] $是多项式时间可溶度或NP-HARD。该结果也可以看作是针对有限评估的CSP（Thapper andŽivný2016）的一般二分法定理的锐化定理的锐化。 在本文中，我们考虑了一个定向版本$ \ oferrightArrow {0} $ - ext $ [μ]最小0-延迟问题的$，其中$μ$和$ c $不认为是对称的。我们将0- ext $ [μ] $的NP硬度条件扩展到$ \ oferrightArrow {0} $ - ext $ [μ] $：如果$μ$不能表示为具有轨道不变的可定向模块图的最短路径，则用orbit-rbit Invariant the odriant ovinected''''expected'''''''我们还显示部分相反：如果$μ$是具有轨道不变的指向边缘长度的模块化晶格的指示度量，则$ \ oferrightArrow {0} $ - ext $ [μ] $是可操作的。我们进一步提供了$ \ oferrightArrow {0} $ - ext $ [μ] $的新的NP硬度条件特征，并为$μ$是恒星的指示度量的情况下建立二分法。
For a metric $μ$ on a finite set $T$, the minimum 0-extension problem 0-Ext$[μ]$ is defined as follows: Given $V\supseteq T$ and $\ c:{V \choose 2}\rightarrow \mathbf{Q_+}$, minimize $\sum c(xy)μ(γ(x),γ(y))$ subject to $γ:V\rightarrow T,\ γ(t)=t\ (\forall t\in 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. Karzanov and Hirai established a complete classification of metrics $μ$ for which 0-Ext$[μ]$ is polynomial time solvable or NP-hard. This result can also be viewed as a sharpening of the general dichotomy theorem for finite-valued CSPs (Thapper and Živný 2016) specialized to 0-Ext$[μ]$. In this paper, we consider a directed version $\overrightarrow{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 $\overrightarrow{0}$-Ext$[μ]$: If $μ$ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed'' edge-length, then $\overrightarrow{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 $\overrightarrow{0}$-Ext$[μ]$ is tractable. We further provide a new NP-hardness condition characteristic of $\overrightarrow{0}$-Ext$[μ]$, and establish a dichotomy for the case where $μ$ is a directed metric of a star.
