Minimum 0-Extension Problems on Directed Metrics

Abstract

For a metric $\mu$ on a finite set $T$, the minimum 0-extension problem 0-Ext$[\mu ]$ is defined as follows: Given $V\supseteq T$ and $c:\left(\genfrac{}{}{0ex}{}{V}{2}\right)\to {\mathbf{Q}}_{+}$, minimize $\sum c(xy)\mu (\gamma (x),\gamma (y))$ subject to $\gamma :V\to T,\gamma (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 $\mu$ for which 0-Ext$[\mu ]$ 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$[\mu ]$. In this paper, we consider a directed version $\overrightarrow{0}$-Ext$[\mu ]$ of the minimum 0-extension problem, where $\mu$ and $c$ are not assumed to be symmetric. We extend the NP-hardness condition of 0-Ext$[\mu ]$ to $\overrightarrow{0}$-Ext$[\mu ]$: If $\mu$ cannot be represented as the shortest path metric of an orientable modular graph with an orbit-invariant ``directed'' edge-length, then $\overrightarrow{0}$-Ext$[\mu ]$ is NP-hard. We also show a partial converse: If $\mu$ is a directed metric of a modular lattice with an orbit-invariant directed edge-length, then $\overrightarrow{0}$-Ext$[\mu ]$ is tractable. We further provide a new NP-hardness condition characteristic of $\overrightarrow{0}$-Ext$[\mu ]$, and establish a dichotomy for the case where $\mu$ is a directed metric of a star.