Discrete convexity and polynomial solvability in minimum 0-extension problems (Q5962712): Difference between revisions

A \(0\)-extension of a graph \(G\) is a metric \(d\) on a set \(V\) containing the vertex set \(V_{G}\) of \(G\) such that \(d\) extends the shortest path metric of \(G\) and for all \(x \in V\) there exists a vertex \(s\) in \(G\) with \(d(x,s)=0\). The minimum \(0\)-extension problem \(0-\mathrm{Ext}[G]\) on \(G\) is: given a set \(V \supseteq V_{G}\) and a non-negative cost function \(c\) defined on the set of all pairs of \(V\), find a \(0\)-extension \(d\) of \(G\) which minimizes \(\sum _{xy} c(x,y)d(x,y)\). \(0-\mathrm{Ext}[G]\) generalizes a number of basic combinatorial optimization problems, such as the minimum \((s,t)\)-cut problem or the multiway cut problem on \(m\) terminals. It is equivalent to the classical multifacility location problem, which has applications in computer vision and machine learning. Karzanov raised the question: what are the graphs \(G\) for which \(0-\mathrm{Ext}[G]\) is solvable in polynomial time? He proved the polynomial solvability of \(0-\mathrm{Ext}[G]\) for a large class of modular graphs, and he showed that \(0-\;mathrm{Ext}[G]\) is NP-hard if \(G\) is not modular or not orientable. The author of this paper proves the converse: if \(G\) is orientable and modular, then \(0-\mathrm{Ext}[G]\) can be solved in polynomial time. For the proof, he develops a theory of discrete, convex functions on orientable, modular graphs, similar to the work of Murota, and he utilizes a recent result of Thapper and Živnỳ on valued \(CSP\).