A fast algorithm for the generalized parametric minimum cut problem and applications

Many combinatorial optimization problems are solved by a sequence of network flow computations on a network whose edge capacities are given as a function of a parameter-lambda. Recently Gallo et al made a major advance in solving such parametric flow problems. They showed that for an important class of networks, called monotone parametric flow networks, a sequence of O(n) flow computations could be solved in the same worst-case time bound as a single flow. However, these results require one of two special assumptions: either that the lambda-values are presented in increasing or decreasing order; or that the edge capacity functions are affine functions of lambda. In this paper the authors show how to remove both of these assumptions while obtaining the same running times as Gallo. This observation generalizes and unifies the two major results of Gallo, and allows its ideas to be applied to many new combinatorial problems. Of greatest importance, it allows the efficient application of binary search and successive binary search to a sequence of network flow problems.