Generalized minimum 0-extension problem and discrete convexity

Given a fixed finite metric space (V,μ ) ( V , μ ) , the minimum 0-extension problem , denoted as 0-Ext[μ ] 0 - Ext [ μ ] , is equivalent to the following optimization problem: minimize function of the form min x∈ Vⁿ ∑ ᵢ fᵢ(xᵢ) + ∑ ᵢⱼ cᵢⱼ0.5ptμ (xᵢ,xⱼ) min x ∈ V n ∑ i f i ( x i ) + ∑ ij c ij μ ( x i , x j ) where fᵢ:V→ R f i : V → R are functions given by fᵢ(xᵢ)=∑ v∈ V cᵥᵢ0.5ptμ (xᵢ,v) f i ( x i ) = ∑ v ∈ V c vi μ ( x i , v ) and cᵢⱼ,cᵥᵢ c ij , c vi are given nonnegative costs. The computational complexity of 0-Ext[μ ] 0 - Ext [ μ ] has been recently established by Karzanov and by Hirai: if metric μ μ is orientable modular then 0-Ext[μ ] 0 - Ext [ μ ] can be solved in polynomial time, otherwise 0-Ext[μ ] 0 - 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^ L ♮ -convex functions. We consider a more general version of the problem in which unary functions fᵢ(xᵢ) f i ( x i ) can additionally have terms of the form cuv;i0.5ptμ (xᵢ,,v\) c u v ; i μ ( x i , { u , v } ) for ,\!0.5pt0.5ptv\∈ F { u , v } ∈ F , where set F⊆ ( arraycV\\ 2array) F ⊆ V 2 is fixed. We extend the complexity classification above by providing an explicit condition on (μ ,F) ( μ , 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 0-Ext[μ ] 0 - Ext [ μ ] on orientable modular graphs.