A note on the parametric maximum flow problem and some related reoptimization issues

In this paper, we will extend the results about the parametric maximum flow problem to networks in which the parametrization of the arc capacities can involve both the source and the sink, as in Gallo et al., and also an additional node. We will show that the minimum cuts of the investigated networks satisfy a relaxed form of the generalized nesting property. A consequence is that the corresponding parametric maximum flow value function has at most n − 1 breakpoints. All the minimum cut capacities can therefore be computed by O(1) maximum flow computations. We will show then that, given O(n) increasing values of the parameter, it is possible to compute the corresponding maximum flows by O(1) maximum flow computations, by suitably extending Goldberg and Tarjan's maximum flow algorithm.