Structural and algorithmic properties for parametric minimum cuts

• 成果类型: Article
• 署名作者: Granot, Frieda; McCormick, S. Thomas; Queyranne, Maurice; Tardella, Fabio
• 署名单位: Sapienza University Rome
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0463-1
• 发表日期: 2012
• 页码: 337-367
• 关键词: submodular function; minimization; base

摘要

We consider the minimum s, t-cut problem in a network with parametrized arc capacities. Following the seminal work of Gallo et al. (SIAM J. Comput. 18(1):30-55, 1989), classes of this parametric problem have been shown to enjoy the nice Structural Property that minimum cuts are nested, and the nice Algorithmic Property that all minimum cuts can be computed in the same asymptotic time as a single minimum cut by using a clever Flow Update step to move from one value of the parameter to the next. We present a general framework for parametric minimum cuts that extends and unifies such results. We define two conditions on parametrized arc capacities that are necessary and sufficient for (strictly) decreasing differences of the parametric cut function. Known results in parametric submodular optimization then imply the Structural Property. We show how to construct appropriate Flow Updates in linear time under the above conditions, implying that the Algorithmic Property also holds under these conditions. We then consider other classes of parametric minimum cut problems, without decreasing differences, for which we establish the Structural and/or the Algorithmic Property, as well as other cases where nested minimum cuts arise.