Chapter 7

Many problems can evolve from the Bipartite Matching problem, such as the perfect matching problem, the assigning-job-to-machine problem, and what we focus on this chapter-network flow problem.

The section first introduces the maximum-flow problem. A flow network is a graph such that each edge is assigned with a positive number called capacity, a single source node s and sink node t. A flow through a network is a function f:E-R+ (from edges to a positive number, that is the amount of flow), such that f satisfy two properties: capacity condition and conservation condition, to ensure the flow function to physically make sense. The value of a flow is defined as the amount of flow generated at the source. The maximum-flow problem is to find a way to maximum the value of the flow of a given flow network. We first want to try to apply greedy algorithm. But it is not hard to find a counter example of just pushing the flow to the network with greedy algorithm. In fact, we need a more generalized “push”. We not only shall push the flow forwards, but also push the flow backward on edges that are already carrying flow. Because in this way, our network becomes more “flexible”-we can divert the flow to more directions. Using this idea, we define a new and useful term: residual graph, which satisfies the following requirements: the nodes are the same as the original graph; the original edges will have f(e)<ce capacities; the backward edges will have f(e) capacities. Then we define a function, called augment(f,P) to add a new flow to the residual graph and update the residual graph. Provided that the path P can be effectively determined, we now can write down the Ford-Fulkerson Algorithm. One limit of the algorithm is that the capacities as well as the value of flow has to be positive integer. Only in this way, we can assure the termination of the F-F algorithm, which is going to be within C iteration, where C is the total possible flow out of the source. The F-F Algorithm thus has a running time O(mC). I have two comments as to the F-F algorithm, 1, in real life, the reverse flow may not be possible at most of the times; 2, in real life, very possibly, the capacity is not all in integer. But the idea is still very neat. Readability is 7.

The section further continues the analysis of the F-F algorithm. If we separate the nodes into two sets, A, B such that s in A, t in B, we denote the s-t cut as (A,B), the capacity of the cut as c(A,B). Two important observations are: 1, f be any s-t flow, (A,B) any cut, v(f)=fout(A)-fin(A) (we can intuitively see it by thinking that all the flow must come across the cut at some pt) 2, Let f be any s-t flow, (A,B) s-t cut, v(f)⇐c(A,B). (this can be visualized the same way as the proceeding property) Now, we can use some particular (A,B) in a graph– the one such that c(A,B) having minimum value, to determine the maximum possible flow, which also obviously makes sense. The theorem can be stated as: if we can find a flow such that v(f)=c(A,B), for some A,B, then f is the maximum flow and (A,B) the minimum cut.

The book shows that the F-F gives back the maximum flow, which is also the minimum cut. Hence, in every flow network, there is a flow f and a cut (A,B) so that v(f)=c(A,B),

Note that all the works so far are under the assumption that the edges' capacities are positive integers. Hence we conclude that if all capacities in the flow network are integers, then there is a maximum flow f for which every flow value f(e) is an integer.

Then the section goes to discuss the comment I pulled out at the journal of section1: what if non-integer? If the capacities are positive rational number, it is not hard to adjust the algorithm-find the least common multiplier and multiply it to everything. However, if just real numbers, it is possible for the algorithm to run forever, since we uses the integer fact to assure the termination of the FF algorithm in section 1. Regardless, the mincut=maxflow theorem still holds in this setting. In addition, in real life, mostly we encounter integer or rational capacities.

Since the end of the section solves my concern, the readability is 8.

Notice that in the journal of section 1, I mentioned if the augmented path P is “efficiently” selected and never really talked about how. Because the entire section 3 is going to contribute to the illustration. Suppose we do not do this efficiently, thus if each augmented path increase the flow by 1, the bound C can be really large. The idea is that for each iteration, we hope to gain a flow value as big as possible. The way to do so is that we maintain a scaling parameter and look for paths that have bottleneck capacity of at least that value (by not considering edges whose remaining capacity is lower than that value); if there is no such path, then we reduce the scaling parameter by half. So basically if the parameter is shrunk to 1, then it is the same as increment of 1 in the original method (Gf(delta)=Gf). The number of iterations of the outer while loop in the algorithm provided in the book is easy to be seen as O(log_2 C). It is not hard to see that during the delta-scaling phase, the increment of the augmentation would promote the flow at least O(delta). Consequently, we have,at delta-scaling phase, the maximum flow in the network has value at most v(f)_mdelta where m is the number of edges in the graph. It follows that the number of augmentations in one scaling phase is at most 2m. Hence we can conclude that the upper bound running time of the F-F algorithm is O(m^2log2C). It is not absolutely in poly time. The next section of the book talks about a different approach that makes the solution strictly poly.

Readability is 7.