Discrete convexity and polynomial solvability in minimum 0-extension problems
Discrete convexity and polynomial solvability in minimum 0-extension problems
复制标题
DOI：
10.1007/s10107-014-0824-7
复制
发表时间：
2013-01
影响因子：
2.7
通讯作者：
H. Hirai
中科院分区：
文献类型：
--
作者：
H. Hirai
图的一个扩张是一个度量，一个包含顶点集的集合，使得最短路径度量被扩张，并且对于所有的顶点都存在一个顶点。最小扩张问题0-Exton是：给定一个集合和定义在所有对的集合上的一个非负代价函数，找到一个具有最小值的-扩张。可拓问题推广了许多基本的组合优化问题，如最小割问题和多路割问题。Karzanov证明了0-Ext对某大类模图的多项式可解性，并提出了这样一个问题：什么样的图0-Ext可以在多项式时间内求解？他还证明了0-Exs是NP-难的，如果它不是模的或不可定向的（在某种意义上）。本文证明了匡威：如果0-Extl是可定向的且模的，则0-Extl可以在多项式时间内求解。这就完成了0-Extistracable图的分类。为了证明我们的主要结果，我们开发了一个理论的离散凸函数的定向模图，类似于离散凸分析Murota，并利用最近的结果Thapper和Chaivnnanshan值CSP。
A-extension of graphis a metricon a setcontaining the vertex setofsuch thatextends the shortest path metric ofand for allthere exists a vertexinwith. The minimum-extension problem0-Extonis: given a setand a nonnegative cost functiondefined on the set of all pairs of, find a-extensionofwithminimum. 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 of0-Extfor a certain large class of modular graphs, and raised the question: What are the graphsfor which0-Extcan be solved in polynomial time? He also proved that0-Extis NP-hard ifis not modular or not orientable (in a certain sense). In this paper, we prove the converse: ifis orientable and modular, then0-Extcan be solved in polynomial time. This completes the classification of graphsfor which0-Extis 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 Živný on valued CSP.