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(V3) for arbitrary weight values; O(Ef), where f is the max flow, for integer values. The latter is generally a lot lower that V2, 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.
Isn’t the minimum cut of the blue graph {B-Sink,B-G,F-G,H-Sink}, with a weight of 6+2+3+5=16? Or am I missing something?
Nope, you’re absolutely right. I messed up doing F-F by hand. I’ll correct it, thanks!
I’m very surprised that finding the maximum cut is harder than finding the minimum cut. Why couldn’t you just transform the weights (for instance, by inverting them), find the minimum cut, and use that as the maximum cut of the original graph?
To me, it seems obvious that finding the maximum cut is harder than the minimum cut. That’s because the weights have a lower bound of 0, but no upper bound. Right?
To address Beren’s question, that’s because the two will not necessarily correspond.
Suppose you have a graph with 4 vertices arranged in a square with edges around the perimeter. The lower left vertex is the source S, the upper right is the destination D. The capacities from source to intermediate nodes are 500,000 and 2, respectively. The capacities from intermediate nodes to destination are both 9. If you invert the capacities, and compute the min cut, you find the cut which isolates D gives the min cut: its capacity is 2/9, while the capacity of the only other cut (which isolates S) is a little more than 1/2. However, thus cut is also the min cut without inverting the graph, obviously.
In algebraic terms, computing the inverse min-cut will tell you that 1/x1 + 1/x2 < 1/x3 + 1/x4… This surely does not imply that x1+x2 > x3 + x4.
It is possible that Beren intended a different kind of inversion, where you replace an edge capacity c by the value C – c, where C is the sum of all edge capacities (this “trick” often shows up in dealing with such problems).
Of course, even this doesn’t work, because different cuts may have a different number of edges in them, and so you can’t ‘reverse-engineer’ a min cut from a min cut in the modified graph.
Good point Suresh. I briefly considered the negation of c, but dismissed it (because of negative capacity) without taking the next logical step. Careless me.
Hi Mark,
You are getting closer and closer to Petri Nets.
http://www.informatik.uni-hamburg.de/TGI/PetriNets/
Just add a token economy.
This is mathematical game theory territory.
Thanks Mark, this was one of my favourite areas of the maths that I covered at A-level and it’s great to realise I still enjoy it now!
Actually, I considered both forms of inversion… but I didn’t work it through far enough. Thanks for pointing out the flaws in the idea (:
In the last example, there seems to be a step missing, and a typo.
After starting with ACBD, you seem to abandon it without explanation. CB has been reduced to 3. How does the algorithm decide to throw away the initial choice?
Typo: “Then ABC is an augmenting flow of 3”. Should be ABD?
Hello,
I have a question for you…. What about a kind of Graph where selecting a node *removes* other nodes from the graph? For example, the vertices of the graph are ‘resources’ and some verticies use the same resources as others. You can only select one of those vertices… So I would imagine either you remove it from the graph, or it changes the max flow of those nodes to 0. But I’m not sure. Any thoughts?
Brigham:
You’re talking about something very different from a simple network flow problem. The problem that you’re talking about needs more information in the graph – in addition to capacities, each node needs to have a set of requirements, and a set of products – so that in addition to maximizing the flow, you need to also address the requirements. That’s a pretty general constraint problem; the truly general form of it is NP complete; it’s equivalent to the bag-packing problem.