Discrete convexity and polynomial solvability in minimum 0-extension problems

作者：Hirai Hiroshi^*

来源：Mathematical Programming, 2016, 155(1-2): 1-55.

DOI：10.1007/s10107-014-0824-7

A -extension of graph is a metric on a set containing the vertex set of such that extends the shortest path metric of and for all there exists a vertex in with . The minimum -extension problem 0-Ext on is: given a set and a nonnegative cost function defined on the set of all pairs of , find a -extension of with minimum. The -extension problem generalizes a number of basic combinatorial optimization problems, such as minimum -cut problem and multiway cut problem. Karzanov proved the polynomial solvability of 0-Ext for a certain large class of modular graphs , and raised the question: What are the graphs for which 0-Ext can be solved in polynomial time? He also proved that 0-Ext is NP-hard if is not modular or not orientable (in a certain sense). In this paper, we prove the converse: if is orientable and modular, then 0-Ext can be solved in polynomial time. This completes the classification of graphs for which 0-Ext is tractable. To prove our main result, we develop a theory of discrete convex functions on orientable modular graphs, analogous to discrete convex analysis by Murota, and utilize a recent result of Thapper and A1/2ivnA1/2 on valued CSP.

• 出版日期2016-1