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
Do'stlaringiz bilan baham: 
