DAA

368 Iterative Improvement 2, 2+ 5 0/2 5 1 0/3 0/4 ∞, – 1 0/2 2, 1+ 0/3 3 0/4 6 2, 3+ ∞, – 1 0/3 2 0/ 5 2, 2+ 0/ 2 0/3 0/5 0/2 236 0/1 1 2/2 0/3 0/1 4 4 3, 1+ Queue: 1 2 4 3 5 6 Augment the flow by 2 (the sink’s first label) ↑↑ ↑↑ along the path 1 → 2 → 3 → 6. 5 1, 2+ 0/3 0/4 5 2 2/5 3 2/2 6 2/2 0/3 3 0/4 6 1, 5+ 0/1 0/3 1, 3– 1, 4+ 2/2 4 Queue: 1 4 3 2 5 6 2/5 2 ↑↑↑↑↑ 0/1 4 3, 1+ Augment the flow by 1 (the sink’s first label) along the path 1 → 4 → 3 ← 2 → 5 → 6. 5 5 1/3 1/4 1/3 1/4 1 2/2 2 1/5 3 2/2 6 ∞, – 1 2/2 2 1/5 3 2/2 6 1/3 1/1 1/3 1/1 4 4 2, 1+ Queue: 1 4 No augmenting path (the sink is unlabeled); ↑↑ the current flow is maximal. FIGURE 10.7 Illustration of the shortest-augmenting-path algorithm. The diagrams on the left show the current flow before the next iteration begins; the diagrams on the right show the results of the vertex labeling on that iteration, the augmenting path found (in bold), and the flow before its augmentation. Vertices deleted from the queue are indicated by the ↑ symbol.

10.2 The Maximum-Flow Problem 369 empty, because it contains the sink), then vi is not the source and its immediate predecessor vi−1 on that path belongs to X. Hence, the edge from vi−1 to vi must be an element of the cut C(X, X¯ ). This proves the property in question. The capacity of a cut C(X, X¯ ), denoted c(X, X¯ ), is defined as the sum of capacities of the edges that compose the cut. For the three examples of cuts given above, the capacities are equal to 5, 6, and 9, respectively. Since the number of different cuts in a network is nonempty and finite (why?), there always exists a minimum cut, i.e., a cut with the smallest capacity. (What is a minimum cut in the network of Figure 10.4?) The following theorem establishes an important relationship between the notions of maximum flow and minimum cut. THEOREM (Max-Flow Min-Cut Theorem) The value of a maximum flow in a network is equal to the capacity of its minimum cut. PROOF First, let x be a feasible flow of value v and let C(X, X¯ ) be a cut of capacity c in the same network. Consider the flow across this cut defined as the difference between the sum of the flows on the edges from X to X¯ and the sum of the flows on the edges from X¯ to X. It is intuitively clear and can be formally derived from the equations expressing the flow-conservation requirement and the definition of the flow value (Problem 6b in this section’s exercises) that the flow across the cut C(X, X¯ ) is equal to v, the value of the flow: v = xij − xji. (10.12) i∈X, j ∈X¯ j ∈X¯ , i∈X Since the second sum is nonnegative and the flow xij on any edge (i, j ) cannot exceed the edge capacity uij , equality (10.12) implies that v ≤ xij ≤ uij , i∈X, j ∈X¯ i∈X, j ∈X¯ i.e., v ≤ c. (10.13) Thus, the value of any feasible flow in a network cannot exceed the capacity of any cut in that network. Let v∗ be the value of a final flow x∗ obtained by the augmenting-path method. If we now find a cut whose capacity is equal to v∗, we will have to conclude, in view of inequality (10.13), that (i) the value v∗ of the final flow is maximal among all feasible flows, (ii) the cut’s capacity is minimal among all cuts in the network, and (iii) the maximum-flow value is equal to the minimum-cut capacity. To find such a cut, consider the set of vertices X∗ that can be reached from the source by following an undirected path composed of forward edges with positive unused capacities (with respect to the final flow x∗) and backward edges with positive flows on them. This set contains the source but does not contain the sink: if it did, we would have an augmenting path for the flow x∗, which would

370 Iterative Improvement contradict the assumption that the flow x∗ is final. Consider the cut C(X∗, X∗). By the definition of set X∗, each edge (i, j ) from X∗ to X∗ has zero unused capacity, i.e., xi∗j = uij , and each edge (j, i) from X∗ to X∗ has the zero flow on it (otherwise, j would be in X∗). Applying equality (10.12) to the final flow x∗ and the set X∗ defined above, we obtain v∗ = xi∗j − xj∗i = uij − 0 = c(X∗, X∗), i∈X∗, j ∈X∗ j ∈X∗, i∈X∗ i∈X∗, j ∈X∗ which proves the theorem. The proof outlined above accomplishes more than proving the equality of the maximum-flow value and the minimum-cut capacity. It also implies that when the augmenting-path method terminates, it yields both a maximum flow and a mini- mum cut. If labeling of the kind utilized in the shortest-augmenting-path algorithm is used, a minimum cut is formed by the edges from the labeled to unlabeled ver- tices on the last iteration of the method. Finally, the proof implies that all such edges must be full (i.e., the flows must be equal to the edge capacities), and all the edges from unlabeled vertices to labeled, if any, must be empty (i.e., have zero flows on them). In particular, for the network in Figure 10.7, the algorithm finds the cut {(1, 2), (4, 3)} of minimum capacity 3, both edges of which are full as required. Edmonds and Karp proved in their paper [Edm72] that the number of aug- menting paths needed by the shortest-augmenting-path algorithm never exceeds nm/2, where n and m are the number of vertices and edges, respectively. Since the time required to find a shortest augmenting path by breadth-first search is in O(n + m) = O(m) for networks represented by their adjacency lists, the time efficiency of the shortest-augmenting-path algorithm is in O(nm2). More efficient algorithms for the maximum-flow problem are known (see the monograph [Ahu93], as well as appropriate chapters in such books as [Cor09] and [Kle06]). Some of them implement the augmenting-path idea in a more efficient manner. Others are based on the concept of preflows. A preflow is a flow that satisfies the capacity constraints but not the flow-conservation requirement. Any vertex is allowed to have more flow entering the vertex than leaving it. A preflow- push algorithm moves the excess flow toward the sink until the flow-conservation requirement is reestablished for all intermediate vertices of the network. Faster al- gorithms of this kind have worst-case efficiency close to O(nm). Note that preflow- push algorithms fall outside the iterative-improvement paradigm because they do not generate a sequence of improving solutions that satisfy all the constraints of the problem. To conclude this section, it is worth pointing out that although the initial interest in studying network flows was caused by transportation applications, this model has also proved to be useful for many other areas. We discuss one of them in the next section.

10.2 The Maximum-Flow Problem 371 Exercises 10.2 1. Since maximum-flow algorithms require processing edges in both directions, it is convenient to modify the adjacency matrix representation of a network as follows. If there is a directed edge from vertex i to vertex j of capacity uij , then the element in the ith row and the j th column is set to uij , and the element in the j th row and the ith column is set to −uij ; if there is no edge between vertices i and j , both these elements are set to zero. Outline a simple algorithm for identifying a source and a sink in a network presented by such a matrix and indicate its time efficiency. 2. Apply the shortest-augmenting path algorithm to find a maximum flow and a minimum cut in the following networks. a. 5 2 125 644 346 78 b. 3 24 21 1 44 6 7 35 5 2 3. a. Does the maximum-flow problem always have a unique solution? Would your answer be different for networks with different capacities on all their edges? b. Answer the same questions for the minimum-cut problem of finding a cut of the smallest capacity in a given network. 4. a. Explain how the maximum-flow problem for a network with several sources and sinks can be transformed into the same problem for a network with a single source and a single sink. b. Some networks have capacity constraints on the flow amounts that can flow through their intermediate vertices. Explain how the maximum-flow problem for such a network can be transformed to the maximum-flow problem for a network with edge capacity constraints only. 5. Consider a network that is a rooted tree, with the root as its source, the leaves as its sinks, and all the edges directed along the paths from the root to the leaves. Design an efficient algorithm for finding a maximum flow in such a network. What is the time efficiency of your algorithm? 6. a. Prove equality (10.9).