Structural and algorithmic properties for parametric minimum cuts

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. © 2011 Springer and Mathematical Optimization Society.