Chapter 7.7: Extensions to the Maximum Flow Problem

So far in our maximum flow problems, we've only had a single source s and a single sink t. Now suppose that there can be a set S of sources generating flow and a set T of sinks that can absorb flow. With multiple sources and sinks, it is unclear how to decide which source or sink to favor in a maximization problem. So 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 G=(V,E) with capacities on the edges. Now, associated with each node v in V is a demand d_v. If d_v>0 then the node has a demand of d_v for flow. If the node is a sink then it wants to receive d_v more units of flow that it sends out. If d_v<0 then the node has a supply of -d_v. If the node is a source then it wants to send out -d_v more units of flow than it receives. If d_v=0 then it is neither a sink nor a source. We use S to denote the set of all nodes with positive demand and T to denote the set of all nodes with positive supply.

We say that a circulation with demands {d_v} is a function f that assigns a non-negative real number to each edge and satisfies the following two conditions:

1. (capacity conditions) for each edge e in E, 0≤f(e)≤c_e
2. (demand conditions) for each vertex v in V, f_in(v)-f_out(v)=d_v

Now, instead of considering a maximization problem, we are concerned with a feasibility problem. We want to know whether there exists a circulation that meets conditions (1) and (2). If there exists a feasible circulation with demands {d_v}, then the sum of all d_v's=0.

We can reduce the problem of finding a feasible solution with demands {d_v} to the problem of finding a maximum s-t flow in a different network. This is very similar to the BMP. We will attach a “super-source” s* to each node in S and a “super-sink” t* to each node in T. More specifically, we will 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 d_v and for each node u in S we add an edge (u,s*) with capacity -d_u. The rest of G carries over to G' unchanged. In G', we will be seeking a maximum s*-t* flow.

There is a feasible circulation with demands {d_v} 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.

The graph G has a feasible circulation with demands {d_v} if and only if for all cuts (A,B), the sum of all demands is less than or equal to c(A,B).

In many applications, 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 like the ones we've used previously, but with a lower bound l_e on each edge e. We will assume 0≤l_e≤c_e for each e. A circulation must satisfy the following 2 conditions:

1. for each e in E, l_e≤f(e)≤c_e
2. for every v in V, we have f_in(v)-f_out(v)=d_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.

I would rate this section a 6. It wasn't too hard to understand, but I think the lecture slides will really help a lot.