Maximum Flow and Minimum Cut

I got started on this series about graph theory by writing a post debunking something foolish that George Gilder said about network theory. Today I'm going to talk about one of the classic problems in graph theory, which happens to be a network problem. It's called the maximum flow problem.

The idea is that you have a weighted graph, which is modeling a bunch of places connected by pipes of different sizes. The sizes of the pipes are represented by the weight labels on the edges, which
are called capacities. Pick two nodes in the graph, called the source and the sink, how much can you pump from source to sink without exceeding the capacities of the pipes? That value is called the maximum flow of the graph.

The answer, in a sort of naive sense, is obvious: find the bottleneck. In a problem like this, the flow is going to be constrained by some structure - find that, and it's easy to figure out the maximum flow of the graph is: it's the capacity of the bottleneck.

It turns out that that naive answer is actually pretty deep. There's a theory called the max-flow/min-cut theorem which is just a formalized version of "the bottleneck determines the maximum".

To state the theorem, first we need to introduce the idea of a cut. Suppose you've got a connected graph, G=(V,E). A cut on G is a way of partitioning V into two disjoint sets. A good way of
thinking about it is that any partition of the vertices into disjoint sets is essentially a description of what edges need to be eliminated to split G into two disjoint graphs. The edges between the partitions
are called the cut edges. If G is a weighted graph, then a cut on G has a weight. The weight of a cut is the sum of the weights of the cut edges.

So, for example, look at the graph over to the right. The dotted line represents a cut. The weight of the cut is 4+5+9+7+11+7+3=46.

The minimum cut of a weighted graph G is the the cut of the graph with minimum weight. The minimum cut between two vertices v and w in G is the minimum weight cut of G that puts v and w in different partitions. For example, in the graph below, the minimum cut is shown with a green dotted line, and has weight 16. (In the original version of this post, I messed up my hand-simulation of Ford-Fulkerson, and wound with an incorrect result, which was caught by a commenter. That's why I like computers: I can't do this stuff right by hand, but I can write a program to do it!)

What the max-flow/min-cut theorem says is that the maximum flow in a weighted graph G between a source s and sink k is the weight of the minimum cut of s and k.

Finding the minimum cut of a graph is reasonably easy - I'll show one algorithm that does it in low-order polynomial time. (It's O(V³) for arbitrary weight values; O(Ef), where f is the max flow, for integer values. The latter is generally a lot lower that V², but there's no guarantee.) But interestingly, finding the maximum cut is NP-complete.

The solution that I'm going to show is called the Ford-Fulkerson algorithm. The simplest version of Ford-Fulkerson is only guaranteed to terminate if the capacities are integers. (There's a refinement of the algorithm, called Edmonds-Karp which is guaranteed to terminate for all weights, but it's easiest to explain the simple Ford-Fulkerson; E-K is basically the same idea.)

The Ford-Fulkerson algorithm is really simple. Basically, find a path from the source to the sink. Find the maximum capacity of that path - that is, the smallest weight of any edge on the path. Subtract that amount of capacity from the edges in the path. Now, repeatedly, search for any path through the graph that, if added to the solution, would increase the flow; that's called an augmenting path. If you can find an augmenting path, then add it to the solution; subtract the capacity of the augmenting path from the edges in the path. When you can't find any more augmenting paths, you'll have the maximum flow. Finding augmenting paths is a relatively straightforward search of the edges of the graph - it takes time O(E). With integer weights, the minimum augmenting flow has weight 1, so there will be no more than f edges.)

There's one tricky point in that algorithm, and I'll demonstrate it with an example. Look at the graph over to the right. Suppose that initially, we start with "ACBD", with a max flow of 3. Then we find that "ABCD" is an augmenting path - adding flow ABCD adds a flow of 6 - but it reverses the flow along edge BC. That leaves a capacity of 4 on AB, 1 on CD, and 0 on BC. Then ABC is an augmenting flow of 3 - leaving 1 and AB, and 0 on BD. Then ACD is an augmenting flow - we can add 1 on AC, and one on CD. So the maximum flow is 6+3+1=10.