Generalized minimum 0-extension problem and discrete convexity

Abstract

Given a fixed finite metric space $(V,\mu )$, the {\em minimum $0$-extension problem}, denoted as ${\tt 0\mbox{-}Ext}[μ]$, is equivalent to the following optimization problem: minimize function of the form $\underset{x\in V^n}{\min }{\sum }_i{f}_i(x_i)+{\sum }_{ij}{c}_{ij}\mu (x_i,x_j)$ where $c_{ij},c_{vi}$ are given nonnegative costs and $f_i:V\to \mathbb{R}$ are functions given by $f_i(x_i)={\sum }_{v\in V}{c}_{vi}\mu (x_i,v)$. The computational complexity of ${\tt 0\mbox{-}Ext}[μ]$ has been recently established by Karzanov and by Hirai: if metric $\mu$ is {\em orientable modular} then ${\tt 0\mbox{-}Ext}[μ]$ can be solved in polynomial time, otherwise ${\tt 0\mbox{-}Ext}[μ]$ is NP-hard. To prove the tractability part, Hirai developed a theory of discrete convex functions on orientable modular graphs generalizing several known classes of functions in discrete convex analysis, such as $L^{♮}$-convex functions. We consider a more general version of the problem in which unary functions $f_i(x_i)$ can additionally have terms of the form $c_{uv;i}\mu (x_i,\{u,v\})$ for $\{u,v\}\in F$, where set $F\subseteq \left(\genfrac{}{}{0ex}{}{V}{2}\right)$ is fixed. We extend the complexity classification above by providing an explicit condition on $(\mu ,F)$ for the problem to be tractable. In order to prove the tractability part, we generalize Hirai's theory and define a larger class of discrete convex functions. It covers, in particular, another well-known class of functions, namely submodular functions on an integer lattice. Finally, we improve the complexity of Hirai's algorithm for solving ${\tt 0\mbox{-}Ext}[μ]$ on orientable modular graphs.

accepted to "Mathematical Programming"