Minimum 0-Extension Problems on Directed Metrics

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:{V \choose 2}\rightarrow ${\mathbf{Q}}_{+}$$,minimize$\sum c(xy)\mu(\gamma(x),\gamma(y))$subjectto$\gamma:V\rightarrow 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 \v{Z}ivn'{y} 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.