Start with a directed graph where each edge uv has a capacity c_uv that represents how much flow can be carried by that edge (measured, for example, in gallons of sewage per minute; edges that aren't in the graph have capacity zero). Suppose the flow comes in at a source node s and leaves at a sink node t. How much flow can be pumped through the graph?

Formally, a flow on a directed graph is a function f on pairs of vertices such that

• For any vertices u and v, f_uv = -f_vu. This says that the net flow in one direction is the negative of the net flow in the other.

• For any vertices u and v, f_uv ≤ c_uv. This says that the flow along some edge does not exceed that edge's capacity.

• For any vertex u except s or t, the sum over all of its neighbors v of f_uv is zero (i.e., ∑_v f_uv = 0). This says that flow is neither created nor destroyed at intermediate nodes; instead, it enters the graph at s (for which ∑_v f_sv ≥ 0) and leaves it at t (for which ∑_v f_tv ≤ 0).

A maximum flow is a flow that maximizes ∑_v f_sv. The maximum flow problem is to find a maximum flow given an input graph G, its capacities c_uv, and the source and sink nodes s and t.

1. Applications

Plumbing

After succeeding to the British crown, you inherit a 16th-century Scottish castle with an elaborate plumbing system that has accumulated pipes, junctions, cross-pipes, shunts, one-way valves, sluiceways, bypasses, and clogs over four centuries. You'd like to know if it is safe to install a modern American shower booth with a 2.5 gallon/minute showerhead, or if this will eventually overflow the historic bathtub of James VI/James I. The answer to this problem depends on the solution to maximum flow for the graph representing the plumbing system.

Traffic engineering

Godzilla is on the march, and you have three hours to evacuate Tokyo. Can you do it? If you can write down a graph with an edge for each road and a vertex for each intersection, this is the same as the plumbing problem, with cars replacing graywater.

Matching

You have n widgets to put in n boxes, but the widgets and boxes are highly individualized and not all widgets will fit in all boxes. Given as input a table that specifies which widgets and boxes can go together, find some way to fit all n widgets one to a box. This is a special case of the AssignmentProblem and can be solved by running max-flow on an appropriately-constructed graph.

Public health

Reanimated zombies infected by a virus from outer space are spreading from the meteor impact site at s along a road network represented by a directed graph toward your 16th-century Scottish castle at t. Your advisors tell you it costs c_uv British pounds to blockade road uv. You'd like to find a cheapest set of roads to blockade to keep the zombies away from your new home. This can be solved by exploiting a connection between maximum flows and minimum cuts (described below), where a minimum s-t cut is the cheapest set of edges that separate s from t.

2. The Fold-Fulkerson Flow Flusher

The simplest, though not the most efficient, of the many algorithms that are known for finding max flows is due to Ford and Fulkerson. The essential idea is that any flow that is not maximum can be improved by adjusting flows along some augmenting path, which will be a path that may include both edges in the graph with unused capacity and backwards edges with some flow on them already. This path is found by performing a search in a residual graph which is derived from the original graph G and the flow f, by the rule that edge uv in G_f has capacity c_uv - f_uv. We think of an edge uv as appearing in G_f just in case this residual capacity c_uv - f_uv is greater than zero.¹ By finding a path from s to t in G_f, we have found a sequence of edges with unused capacity; by increasing the flow along this path, we increase the total s-t flow without exceeding the capacity constraints. The algorithm repeats this process until no such augmenting paths exist.

{{{FordFulkerson(G)

• set f[u,v] = 0 for all pairs of vertices u and v set g[u,v] = c(u,v) for all edges uv in G set g[u,v] = 0 for all pairs of vertices u and v where uv is not an edge while true do
  • if there exists an path s, v1, v2, ..., vk, t

    • where g[v, v'] > 0 for each pair of adjacent vertices v, v' in the path,

    then
    • // augment increase f[v,v'] by min g[v,v'] for each such pair v,v' decrease g[v,v'] by min g[v,v'] for each such pair v,v'
    else
    • // no further improvement possible return f

}}}

Note that because f_vu = -f_uv, G_f may contain some edges that are not in G; these correspond to the reverse of edges in G that have some flow on them already. It may seem odd to think that we can increase the total flow by sending flow backwards across an edge in the graph, because the problem doesn't allow us to send flow backwards across edges. But what we are really doing when we send flow across some reversed edge vu is canceling out some of the flow from u to v; this cancellation has the effect of decreasing the amount of flow leaving u and increasing the amount of flow leaving v, which is exactly the same as if we really were sending more flow across some new edge vu.

For example, the picture above shows a flow on a graph G (on top), where each edge is labeled with flow/capacity. The residual graph is shown on the bottom; graph edges are shown in black and reversed edges are shown in blue. There is an s-t path in the residual graph that goes through s,b,a,t; the flow on this augmenting path can be increased by 2, since this is the minimum unused capacity of any edge on the path. The effect of performing this increase is to raise the flow on sb to 2, turn off the flow on ab, and raise the flow on at to 2---this redirects the sa flow across at and uses the capacity formerly needed to carry this flow across bt for 2 new units of flow coming out of sb. The result is a new flow and a new residual graph shown below.

The residual graph now has more edges, because some of the edges in G are only partially used. But there is no path from s to t, so the Ford-Fulkerson algorithm stops, and returns the current flow as its claimed maximum. In the next section, we show that whenever Ford-Fulkerson stops, it has indeed found the maximum flow.

3. Max-flows and min-cuts

To show that no better flow exists that found by Ford-Fulkerson, we'll show that the Ford-Fulkerson flow uses the full capacity of every edge in some s-t cut, where an s-t cut is defined by a partition of the vertices into two sets S and T where s is in S and t is in T, and the edges in the cut are all edges that cross the partition, i.e., all edges uv with u in S and v in T.

Let f' be the final flow produced by the Ford-Fulkerson algorithm, and define S as the set of all vertices reachable from s in the final residual graph G_f', and T as the set of all vertices not in S. Consider some edge uv in the original that crosses the cut; i.e. that has u in S and v in T. Because u is reachable from s in G_f' and v is not, uv cannot appear as an edge in G_f. This means that c_uv - f'_uv = 0 and that uv is saturated---it has no leftover capacity to use. Since this is true for any such edge, the final flow f saturates all edges that cross the cut.

This fact is enough to show that f' is a maximum flow. Consider any other flow f, and recall that f_uv = -f_vu by definition; so for any set A, ∑_{u in A, v in A} f_uv = 0, because every edge appears once as f_uv and once as f_vu. Now compute

• ∑_{u in S, v in G} f_uv

  = ∑_{u in S, v in S} f_uv + ∑_{u in S, v in T} f_uv

  = ∑_{u in S, v in T} f_uv.

This shows that the total net outflow from all nodes in S equals the total flow across the S-T cut. But we also know that the total net outflow from any node in V-{s,t} is zero, so

• ∑_{u in S, v in G} f_uv

  = ∑_{v in G} f_sv + ∑_{u in S-s, v in G} f_uv

  = ∑_{v in G} f_sv.

So the size of the flow equals the flow across the cut. But this is limited by the capacity of the cut, which is the sum of the capacities of the S-T edges:

• ∑_{v in G} f_sv

  = ∑_{u in S, v in T} f_uv

  ≤ ∑_{u in S, v in T} c_uv

  = ∑_{u in S, v in T} f'_uv

  = ∑_{v in G} f_sv.

We've shown a couple of things here. The first is that the size of any s-t flow is bounded by the capacity of any s-t cut, and in particular that the size of the max flow is less than or equal to the capacity of the min cut. The second is that the size of any s-t flow is less than or equal to the size of the Ford-Fulkerson flow, which shows that the Ford-Fulkerson flow is maximum.

But we've shown something else about max flows and min cuts. Because the Ford-Fulkerson flow saturates some cut, its size equals the capacity of some cut---so the size of the maximum flow is at least as big as the size of the minimum cut. Since we already showed it's no bigger, they must be equal. This gives the

Max-flow min-cut theorem

In any graph G with capacities, the maximum size of any s-t flow equals the minimum capacity of any s-t cut.

A consequence of the max-flow min-cut theorem and the analysis above is that finding a maximum flow also finds a minimum cut, by constructing S and T as above. This solves the zombie-diversion problem mentioned previously.

4. Running time of Ford-Fulkerson

Each iteration of Ford-Fulkerson takes O(E) time to find an augmenting path (G_f has at least E and at most 2E edges, so the time is O(V+2E) = O(E+E) = O(E)). Each iteration also increases the flow by at least 1, assuming all capacities are integers. So the maximum number of iterations equals the highest capacity K of any cut in the graph which is bounded by EU where U is the highest edge capacity, giving a running time of O(E² U).

It turns out that if one is particularly foolish in choosing augmenting paths, Θ(EU) is in fact the worst-case number of iterations. A simple example of what can go wrong is depicted below, with the steadily increasing flows shown from top to bottom in the left-hand column and the corresponding residual graphs and augmenting paths (in red) shown on the right. With each augmentation the flow increases by exactly 1 as the algorithm changes its mind about whether to use the middle edge; it takes 200 augmentations before the algorithm terminates, even though choosing the high-capacity top and bottom paths at the start could finish in 2.

But this bad outcome can be avoided by choosing a shortest augmenting path at each step using BreadthFirstSearch. The resulting special case of Ford-Fulkerson is known as Edmonds-Karp after the researchers who proved that it worked. The essential idea of the proof is to show that any edge that is saturated can only reappear in G_f with its source vertex more distant from s than it used to be. It follows that edge edge can be saturated only O(V) times, and since each augmenting path saturates at least one edge, the number of iterations is at most O(VE). This gives a total running time of O(VE²). (See CormenEtAl section 26.2 if you care about the details.)

The max-flow/min-cut problem has been studied very extensively, and still better algorithms exist. The fastest currently known algorithm runs in approximately O(min(E^3/2, V^2/3E)) time, ignoring logarithmic terms; it is due to Goldberg and Rao.²

5. Integer solutions and maximum matchings

• Note that all flows found by FF are integral.
• Reduction of maximum matching to max-flow.

• What about maximum-weight matching? O(V³) Hungarian method described in PapadimitriouSteiglitz Chapter 11.

---

CategoryAlgorithmNotes Volume