PARAMETRIC MAX-FLOW PROBLEMS IN A CLASS OF NETWORKS WITH SERIES-PARALLEL STRUCTURE

Abstract

This paper considers a parametric max flow network problem where arc capacities are not fixed but stated as unknown variables to be determined optimally such that the corresponding max flow satisfies flow requirement between source and sink. For the problem, a max flow algorithm may be adapted as a subroutine to be used recursively in an enumerative solution search until finding the optimal solution. However, such an enumerative approach is not practical because it is not guaranteed to solve the problem in a finite number of steps. Therefore, this paper pays attention to the instance defined in a special class of networks, called basically-series-parallel networks, for which all minimal cutsets can easily be enumerated in polynomial time by introducing a set of network reduction methods, called 2-neighbor-node, parallel and source-delta reductions, while such minimal cutset enumeration itself is NP-hard in general. Once all minimal cutsets are found, the associated parametric max flow problem remains simply to solve in a linear programming approach.