Source code online books for professionals by professionals

reSIDUaL NetWOrKS
one abstraction that is often used to explain the Ford-Fulkerson method and its relatives is residual networks. 
A residual network G
f
 is defined with respect to an original flow network G, as well as a flow f, and is a way of 
representing the traversal rules used when looking for augmenting paths. In G
f
 there is an edge from u to v if (and 
only if) either (1) there is an unsaturated edge (that is, one with residual capacity) from u to v in G or (2) there is a 
positive flow in G from v to u (which we are allowed to cancel).
In other words, our special augmenting traversal in G now becomes a completely normal traversal in G
f
. The 
algorithm terminates when there is no longer a path from the source to the sink in the residual network. while the 
idea is primarily a formal one, making it possible to use ordinary graph theory to reason about the augmentation, 
you could also implement it explicitly, if you wanted (exercise 10-5), as a dynamic view of the actual graph. 
That would allow you to use existing implementations of BFs, and (as you’ll see later) Bellman-Ford and dijkstra 
directly on the residual network.
Minimum Cut
Just like the zero-one flow gave rise to Menger’s theorem, the more general flow problem gives us the max-flow min-
cut theorem of Ford and Fulkerson, and we can prove it in a similar fashion.
3
 If we assume that the only cuts we’re 
talking about are s-t cuts and we let the capacity of a cut be the amount of flow that can be moved across it (that is, the 
sum of the forward-edge capacities), we can show that the following three statements are equivalent:
We have found a flow of size 
•
k, and there is a cut with capacity k.
We have found the maximum flow.
•
There are no augmenting paths.
•
Proving this will give us two things: It will show that the Ford-Fulkerson method is correct, and it means that we 
can use it to also find a minimum cut, which is a useful problem in itself. (I’ll get back to that.)
3
Actually,
 
the proof I used in the zero-one case was just a simplified version of the proof I use here. There are proofs for Menger’s 
theorem that don’t rely on the idea of flow as well.

---

ChApTeR 10 
■
 MATChINgs, CuTs, ANd Flows 
219
As in the zero-one case, the first clearly implies the second. Every unit of flow must pass through any s-t cut, so 
if we have a cut of capacity k, that is an upper limit to the flow. If we have a flow that equals the capacity of a cut, that 
flow must be maximum, while the cut must be minimum. This is a case of what is called duality.
The implication from the second statement (we’ve reached the max) to the third (there are no augmenting paths) 
is once again provable by contradiction. Assume we have reached the maximum, but there is still an augmenting path. 
Then we could use that path to increase our flow, which is a contradiction.
The last step (no augmenting paths means we have a cut equaling the flow) is again shown using the traversal 
to construct a cut. That is, we let S be the set of nodes we can reach in the last iteration, and T is the remainder. Any 
forward edge across the cut must be saturated because otherwise we would have traversed across it. Similarly, any 
backward edge must be empty. This means that the flow going across the cut is exactly equal to its capacity, which is 
what we wanted to show.
Minimum cuts have several applications that don’t really look like max-flow problems. Consider, for example, 
the problem of allocating processes to two processors in a manner that minimizes the communication between them. 
Let’s say one of the processors is a GPU and that the processes have different running times on the two processors. 
Some fit the CPU better, while some should be run on the GPU. However, there might be cases where one fits on the 
CPU and one on the GPU, but where the two communicate extensively with each other. In that case, we might want to 
put them on the same processor, just to reduce the communication costs.
How would we solve this? We could set up an undirected flow network with the CPU as the source and the GPU 
as the sink, for example. Each process would have an edge to both source and sink, with a capacity equal to the time 
it would take to run on that processor. We also add edges between processes that communicate, with capacities 
representing the communication overhead (in extra computation time) of having them on separate processors. The 
minimum cut would then distribute the processes on the two processors in such a way that the total cost is as small as 
possible—a nontrivial task if we couldn’t reduce to the min-cut problem.
In general, you can think of the whole flow network formalism as a special kind of algorithmic machine, and you 
can use it to solve other problems by reduction. The task becomes constructing some form of flow network where a 
maximum flow or minimum cut represents a solution to your original problem.
DUaLItY
There are a couple of examples of duality in this chapter: Maximum bipartite matchings are the dual of minimum 
bipartite vertex covers, and maximum flows are the dual of minimum cuts. There are several similar cases as well, 
such as the maximum tension problem, which is the dual of the shortest path problem. In general, duality involves 
two optimization problems, the primal and the dual, where both have the same optimization cost, and solving one 
will solve the other. More specifically, for a maximization problem A and a minimization problem B, we have weak 
duality if the optimal solution for A is less than or equal to the optimal solution for B. If they are equal (as for the 
max-flow min-cut case), we have strong duality. If you want to know more about duality (including some rather 
advanced material), take a look at Duality in Optimization and Variational Inequalities, by go and Yang.
Cheapest Flow and the Assignment Problem
*
Before leaving the topic of flow, let’s take a look at an important and rather obvious extension; let’s find the cheapest 
maximum flow. That is, we still want to find the maximum flow, but if there is more than one way to achieve the same 
flow magnitude, we want the cheapest one. We formalize this by adding costs to the edges and define the total cost as 
the sum of w(e)·f(e) over all edges e, where w and f are the cost and flow functions, respectively. That is, the cost is per