Chapter 7.7: Extensions to the Maximum-Flow Problem
Many problems with a nontrivial combinatorial search component can be solved in polynomial time because they can be reduced to the problem of finding a maximum flow or a minimum cut in a directed graph.
Circulations with Demands
Suppose there can be a set S of sources generating flow, and a set T of sinks that can absorb flow. Instead of maximizing the flow value, we will consider a problem where sources have fixed supply values and sinks have fixed demand values, and our goal is to ship flow from nodes with available supply to those with given demands.
Thus we are given a flow network, and now, associated with each node v is a demand dv. If dv > 0, this node has a demand for flow; this node is a sink. If dv < 0, this node has a supply of -dv; this node is a source. If dv = 0, then the node is neither a source nor a sink.
We can reduce the problem of finding a feasible circulation with demands {dv} to the problem of finding a maximum s-t flow in a different network. We attach a “super-source” s* to each node in S, and a “super-sink” t* to each node in T. More specifically, we create a graph G' from G by adding new nodes s* and t* to G. For each node v in T, we add an edge v,t* with capacity dv. For each node u in S, we add an edge s*,u with capacity -du. We carry the remaining structure of G over to G' unchanged. In this graph G', we will be seeking a maximum s*-t* flow. Note that there cannot be an s*-t* flow in G' of value greater than D - the total demand.
There is a feasible circulation with demands {dv} in G if and only if the maximum s*-t* flow in G' has value D. If all capacities and demands in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer valued.
Circulations with Demands and Lower Bounds
We not only want to satisfy demands at various nodes; we also want to force the flow to make use of certain edges. This can be enforced by placing lower bounds on edges. Consider a flow network G with a capacity ce and a lower bound le on each edge e. The given quantities have the same meaning as before, and now a lower bound le means that the flow value on e must be at least le.
- Capacity conditions : For each e in E, we have le ⇐ f(e) ⇐ ce.
- Demand conditions : For every v in V, we have fin(v) - fout(v) = dv
f0in(v) - f0out(v) = Lv. If Lv = dv, then we have satisfied the demand condition at v; but if not, then we need to superimpose a circulation f1 on top of f0 that will clear the remaining “imbalance” at v.
There is a feasible circulation in G if and only if there is a feasible circulation in G'. If all demands, capacities, and lower bounds in G are integers, and there is a feasible circulation, then there is a feasible circulation that is integer-valued.
This chapter really helped put into perspective the possibilities for network-flow algorithms. 10/10.
