Polymatroidal flows with lower bounds (Q581209)

Ordinary network flow theory has a number of interesting theorems dealing with the maximum flow problem: integer solutions, polynomial bounds, max- flow-min-cut theorem and augmenting path algorithms. These results have previously been extended to polymatroidal networks. These are network flow problems where capacity constraints are imposed on the set of arcs into and out of each node, as opposed to capacity constraints on individual arcs. This paper examines the extension of the four main results of network flow theory to the case where lower bounds are imposed to the arc sets, in addition to the capacity bounds. First, it is pointed out that for general constraints, the problem of finding a feasible solution is NP- hard, since it is equivalent to the Hamiltonian circuit problem. Then, a subset of bounds, namely those that have the property of being compliant, are defined. For compliant bounds, it is always possible to compensate a flow variation on one arc by a corresponding and opposite flow variation on a single arc adjacent to the node. From this property, the authors demonstrate the four theorems concerning the maximum flow, and prove an \(O(m^ 5d)\) bound for the maximum flow computation, where m is the number of arcs and d the time required to compute a feasible solution.