This chapter goes back to the bipartite matching problem from the beginning of the term. One problem is to determine the size of the largest matching in a bipartite graph, which needs new techniques to solve. They develop a new class of problems - network flow problems - that include bipartite matching as a special case. They develop a polynomial-time algorithm for the Maximum-Flow Problem and show how it works for bipartite matching and other problems. The first section models transportation networks with graphs. Edges have capacities, and there are source and sink nodes in the graph. Traffic is referred to as flow. A flow network is a directed graph where each edge has a nonnegative capacity, and there's a single source s and a single sink node t (other than s and t, the nodes are internal nodes). No edge enters s, no edge leaves t. All capacities are integers. There's at least one edge incident to each node. Flow has to be between zero and the capacity for every edge. Except for s and t, the amount of flow entering a node has to equal the amount leaving the node. So a goal is to figure out how to get maximum flow from s to t on a graph. They go through an example of why greedy doesn't work. Then they get into the Ford-Fulkerson algorithm. You keep track of the graph and the flow on every edge and also of a residual graph. In the residual graph, the “remaining capacity” (i.e. capacity minus flow) is represented by a forward edge, the flow is represented by a backward edge. Augmenting paths in the residual graph are paths from s to t (i.e. paths that you can add more flow to). The bottleneck of the augmenting path is the minimum residual capacity of any edge in the augmenting path. So in order to augment a path, you just push as much flow as possible (determined by the bottleneck) onto every edge in that path (and update the residual graph). They go through and show that this gives a flow and doesn't violate any of the rules (like conservation). Then they give the Ford-Fulkerson algorithm: all flows 0 in the graph to begin with, while there's an augmenting path in the residual graph, augments the path and updates the residual graph. They prove that it will terminate because every iteration increases the overall flow values (and for integer costs, that has to be at least one each time), and they put an upper bound on the number of iterations, by using C, which is the capacity out of s. If the overall flow is increased by one each iteration, then the absolute highest it can go is C. If these capacities are all integers, then Ford-Fulkerson completes in O(mC) time because each iteration takes O(m) work to find an augmenting path.
None. The non-integer, non-rational-number idea is pretty interesting; I think it would be neat to see how that runs (I mean, obviously I could make one and go through it … maybe I will sometime).
Great :)
This section is an analysis of the Ford-Fulkerson algorithm. They show that the flow is the max possible value for any flow in the graph. If you divide the nodes into two sets A and B such that s is in A and t is in B, then the capacity of the cut is the sum of the capacities of the edges out of A. Cuts provide upper bounds on the values of flows. v(f) = fout(A)-fin(A). They go on to show that the max flow is upper bounded by the capacity of every cut, so there can't be a cut with value less than the flow. In order to show that the flow is the maximum psosible value of any flow in G, we use this fact. We show that there's some cut where the flow is equal to the value of the cut. That means that the flow is max and that that particular cut is min. They prove that this is the case and that this is all that's necessary to show that F-F is optimal. The residual graph from F-F will also give us the min cut pretty directly. It's all of the nodes reachable from s. There's a flow and a cut in every flow network such that their values are equal (pretty cool!), and the max value of an s-t flow is equal to the capacity of an s-t cut in every flow network. Integers vs. real numbers: for rational numbers, you can multiply by some constant to turn the whole thing into integers. No biggie. But irrational numbers create a little bit more of a problem (ok … a big problem): the F-F might not terminate! But the max-cut-min-flow thing still works. In real problems, there wouldn't be irrational numbers, but the F-F can take a long time to complete if we don't make good choices of augmenting paths. That's improved upon in the next section.
None.
Great :) Except I felt like they kept giving the same facts over and over and over in this section … they're all so closely related and follow pretty directly from each other.
It's important for the running time of this algorithm that you pick good augmenting paths. They give an example of when choosing the wrong path could be especially bad. So in order to do make a running time improvement, we need to choose paths with high bottlenecks first (that way we make the most “progress” toward the max flow in each step). But instead of trying to find the one with the highest bottleneck capacity, we maintain a “scaling parameter” delta and look for paths with a bottleneck of at least delta. So we keep track of the residual graph that only has edges of at most delta capacity. Delta starts out as a the highest power of two that is no larger than the maximum capacity out of s, and after we've found all of the augmenting paths in the residual graph of that delta, we divide delta by two and repeat (see algorithm p353). This is really just another implementation of Ford-Fulkerson (i.e. it will still work!), and it's bounded by an O(m^2(logC)) running time. This is because every augmentation in the delta-scaling phase increases the flow value by at least delta, and the max flow in the network has value at most v(f)+m*delta. It makes sense to look for an algorithm with a running time that only depends on m and n (instead of C). Some have been found that run in O(mnlogn), O(n^3), etc … that's called strongly polynomial, and it's discussed in the next section.
None.
Wonderful :)