Authors: Frieda Granot S Thomas McCormick Maurice Queyranne Fabio Tardella
Publish Date: 2011/06/26
Volume: 135, Issue: 1-2, Pages: 337-367
Abstract
We consider the minimum s tcut problem in a network with parametrized arc capacities Following the seminal work of Gallo et al SIAM J Comput 18130–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
Keywords: