6.046J Lecture 13: Network Flow

Lecture 13 Network Flow Supplemental reading in CLRS: Sections 26.1 and 26.2 When we concerned ourselves with shortest paths and minimum spanning trees, we interpreted the edge weights of an undirected graph as distances. In this lecture, we will ask a question of a different sort. We start with a directed weighted graph G with two distinguished vertices s (the source) and t (the sink). We interpret the edges as unidirectional water pipes, with an edge’s capacity indicated by its weight. The maximum flow problem then asks, how can one route as much water as possible from s to t? To formulate the problem precisely, let’s make some definitions. Definition. A flow network is a directed graph G = (V , E) with distinguished vertices s (the source) and t (the sink), in which each edge (u, v) ∈ E has a nonnegative capacity c(u, v). We require that E never contain both (u, v) and (v, u) for any pair of vertices u, v (so in particular, there are no loops). Also, if u, v ∈ V with (u, v) 6∈ E, then we define c(u, v) to be zero. (See Figure 13.1). In these notes, we will always assume that our flow networks are finite. Otherwise, it would be quite difficult to run computer algorithms on them. Definition. Given a flow network G = (V , E), a flow in G is a function f : V × V → R satisfying 1. Capacity constraint: 0 ≤ f (u, v) ≤ c(u, v) for each u, v ∈ V 12 16 s 20 4 9 t 7 4 13 14 Figure 13.1. A flow network. 2. Flow conservation: for each u ∈ V \ { s, t}, we have1 X f (v, u) = v∈V | X f (u, v) . v∈V {z } flow into u | {z } flow out of u In the case that flow conservation is satisfied, one can prove (and it’s easy to believe) that the net flow out of s equals the net flow into t. This quantity is called the flow value, or simply the magnitude, of f . We write X X X X |f | = f (s, v) − f (v, s) = f (v, t) − f (t, v). |{z} v∈V v∈V v∈V v∈V flow value Note that the definition of a flow makes sense even when G is allowed to contain both an edge and its reversal (and therefore is not truly a flow network). This will be important in §13.1.1 when we discuss augmenting paths. 13.1 The Ford–Fulkerson Algorithm The Ford–Fulkerson algorithm is an elegant solution to the maximum flow problem. Fundamentally, it works like this: 1 2 while there is a path from s to t that can hold more water do Push more water through that path Two notes about this algorithm: • The notion of “a path from s to t that can hold more water” is made precise by the notion of an augmenting path, which we define in §13.1.1. • The Ford–Fulkerson algorithm is essentially a greedy algorithm. If there are multiple possible augmenting paths, the decision of which path to use in line 2 is completely arbitrary.2 Thus, like any terminating greedy algorithm, the Ford–Fulkerson algorithm will find a locally optimal solution; it remains to show that the local optimum is also a global optimum. This is done in §13.2. 13.1.1 Residual Networks and Augmenting Paths The Ford–Fulkerson algorithm begins with a flow f (initially the zero flow) and successively improves f by pushing more water along some path p from s to t. Thus, given the current flow f , we need 1 In order for a flow of water to be sustainable for long periods of time, there cannot exist an accumulation of excess water anywhere in the pipe network. Likewise, the amount of water flowing into each node must at least be sufficient to supply all the outgoing connections promised by that node. Thus, the amount of water entering each node must equal the amount of water flowing out. In other words, the net flow into each vertex (other than the source and the sink) must be zero. 2 There are countless different versions of the Ford–Fulkerson algorithm, which differ from each other in the heuristic for choosing which augmenting path to use. Different situations (in which we have some prior information about the nature of G) may call for different heuristics. Lec 13 – pg. 2 of 11 a way to tell how much more water a given path p can carry. To start, note that a chain is only as strong as its weakest link: if p = 〈v0 , . . . , vn 〉, then µ ¶ amount of additional water that can flow through p ¶ µ amount of additional water that . 1≤ i ≤ n can flow directly from v i −1 to v i min = All we have to know now is how much additional water can flow directly between a given pair of vertices u, v. If (u, v) ∈ E, then clearly the flow from u to v can be increased by up to c(u, v) − f (u, v). Next, if (v, u) ∈ E (and therefore (u, v) 6∈ E, since G is a flow network), then we can simulate an increased flow from u to v by decreasing the throughput of the edge (v, u) by as much as f (v, u). Finally, if neither (u, v) nor (v, u) is in E, then no water can flow directly from u to v. Thus, we define the residual capacity between u and v (with respect to f ) to be     c(u, v) − f (u, v) if (u, v) ∈ E c f (u, v) = f (v, u) (13.1) if (v, u) ∈ E   0 otherwise. When drawing flows in flow networks, it is customary to label an edge (u, v) with both the capacity c(u, v) and the throughput f (u, v), as in Figure 13.2. Next, we construct a directed graph G f , called the residual network of f , which has the same vertices as G, and has an edge from u to v if and only if c f (u, v) is positive. (See Figure 13.2.) The weight of such an edge (u, v) is c f (u, v). Keep in mind that c f (u, v) and c f (v, u) may both be positive for some pairs of vertices u, v. Thus, the residual network of f is in general not a flow network. Equipped with the notion of a residual network, we define an augmenting path to be a path from s to t in G f . If p is such a path, then by virtue of our above discussion, we can perturb the flow f at the edges of p so as to increase the flow value by c f (p), where c f (p) = min c f (u, v). (u,v)∈ p (13.2) The way to do this is as follows. Given a path p, we might as well assume that p is a simple path.3 In particular, p will never contain a given edge more than once, and will never contain both an edge and its reversal. We can then define a new flow f 0 in the residual network (even though the residual network is not a flow network) by setting ( f 0 (u, v) = c f (p) if (u, v) ∈ p 0 otherwise. Exercise 13.1. Show that f 0 is a flow in G f , and show that its magnitude is c f (p). ¯ ¯ ¯ ¯ Finally, we can “augment” f by f 0 , obtaining a new flow f ↑ f 0 whose magnitude is ¯ f ¯ + ¯ f 0 ¯ = 3 Recall that a simple path is a path which does not contain any cycles. If p is not simple, we can always pare p down to a simple path by deleting some of its edges (see Exercise B.4-2 of CLRS, although the claim I just made is a bit stronger). Doing so will never decrease the residual capacity of p (just look at (13.2)). Lec 13 – pg. 3 of 11 Flow/Capacity 12/12 11/16 15/20 1/4 s 4/9 7/7 t 8/13 4/4 11/14 Residual Network 12 5 5 4 11 s 3 5 1 4 15 t 7 8 4 5 3 11 Augmented Flow 12/12 11/16 19/20 1/4 s 0/9 7/7 t 12/13 4/4 11/14 New Residual Network 12 1 5 11 s 19 3 1 9 t 7 12 4 1 3 11 Figure 13.2. We begin with a flow network G and a flow f : the label of an edge (u, v) is “a/b,” where a = f (u, v) is the flow through the edge and b = c(u, v) is the capacity of the edge. Next, we highlight an augmenting path p of capacity 4 in the residual network G f . Next, we augment f by the augmenting path p. Finally, we obtain a new residual network in which there happen to be no more augmenting paths. Thus, our new flow is a maximum flow. Lec 13 – pg. 4 of 11 ¯ ¯ ¯ f ¯ + c f (p). It is defined by4 ¡ 0 ¢ f ↑ f (u, v) =     f (u, v) + c f (p) f (u, v) − c f (p)    f (u, v) if (u, v) ∈ p and (u, v) ∈ E if (v, u) ∈ p and (u, v) ∈ E otherwise. Lemma 13.1 (CLRS Lemma 26.1). Let f be a flow in the flow network G = (V , E) and let f 0 be a flow in the residual network G f . Let f ↑ f 0 be the augmentation of f by f 0 , as described in (13.3). Then ¯ ¯ ¯ ¯ ¯ ¯ ¯ f ↑ f 0¯ = ¯ f ¯ + ¯ f 0¯ . Proof sketch. First, we show that f ↑ f 0 obeys the capacity constraint for each edge in E and obeys flow conservation for ¯each vertex in V \ { s, t}. Thus, f ↑ f 0 is truly a flow in G. Next, we obtain ¯ ¯ ¯ ¯ ¯ the identity ¯ f ↑ f 0 ¯ = ¯ f ¯ + ¯ f 0 ¯ by simply expanding the left-hand side and rearranging terms in the summation. 13.1.2 Pseudocode Implementation of the Ford–Fulkerson Algorithm Now that we have laid out the necessary conceptual machinery, let’s give more detailed pseudocode for the Ford–Fulkerson algorithm. Algorithm: F ORD –F ULKERSON(G) 1 B Initialize flow f to zero 2 for each edge (u, v) ∈ E do (u, v). f ← 0 B The following line runs a graph search algorithm (such as BFS or DFS)∗ to find a path from s to t in G f while there exists a path p : s t in G f do © ª c f (p) ← min c f (u, v) : (u, v) ∈ p for each edge (u, v) ∈ p do B Because (u, v) ∈ G f , it must be the case that either (u, v) ∈ E or (v, u) ∈ E. B And since G is a flow network, the “or” is exclusive: (u, v) ∈ E xor (v, u) ∈ E. if (u, v) ∈ E then (u, v). f ← (u, v). f + c f (p) else (v, u). f ← (v, u). f − c f (p) 3 4 5 6 7 8 9 10 11 12 13 ∗ For more information about breath-first and depth-first searches, see Sections 22.2 and 22.3 of CLRS. Here, we use the notation (u, v). f synonymously with f (u, v); though, the notation (u, v). f suggests a convenient implementation decision in which we attach the value of f (u, v) as satellite data to the 4 In a more general version of augmentation, we don’t require p to be a simple path; we just require that f 0 be some flow in the residual network G f . Then we define ( 0 f (u, v) = f (u, v) + f 0 (u, v) − f 0 (v, u) if (u, v) ∈ E 0 otherwise. Lec 13 – pg. 5 of 11 (13.3) edge (u, v) itself rather than storing all of f in one place. Also note that, because we often need to consider both f (u, v) and f (v, u) at the same time, it is important that we equip each edge (u, v) ∈ E with a pointer to its reversal (v, u). This way, we may pass from an edge (u, v) to its reversal (v, u) without performing a costly search to find (v, u) in memory. We defer the proof of correctness to §13.2. We do show, though, that the Ford–Fulkerson algorithm halts if the edge capacities are integers. Proposition 13.2. If the edge capacities of G are integers, then the Ford–Fulkerson algorithm termi¡ ¢ nates in time O E · | f ∗ | , where | f ∗ | is the magnitude of any maximum flow for G. Proof. Each time we choose an augmenting path p, the right-hand side of (13.2) is a positive integer. Therefore, each time we augment f , the value of | f | increases by at least 1. Since | f | cannot ever exceed | f ∗ |, it follows that lines 5–13 are repeated at most | f ∗ | times. Each iteration of lines 5–13 takes O(E) time if we use a breadth-first or depth-first search in line 5, so the total running time of ¡ ¢ F ORD –F ULKERSON is O E · | f ∗ | . Exercise 13.2. Show that, if the edge capacities of G are rational numbers, then the Ford–Fulkerson algorithm eventually terminates. What sort of bound can you give on its running time? Proposition 13.3. Let G be a flow network. If all edges in G have integer capacities, then there exists a maximum flow in G in which the throughput of each edge is an integer. One such flow is given by running the Ford–Fulkerson algorithm on G. Proof. Run the Ford–Fulkerson algorithm on G. The residual capacity of each augmenting path p in line 5 is an integer (technically, induction is required to prove this), so the throughput of each edge is only ever incremented by an integer. The conclusion follows if we assume that the Ford–Fulkerson algorithm is correct. The algorithm is in fact correct, by Corollary 13.8 below. Flows in which the throughput of each edge is an integer occur frequently enough to deserve a name. We’ll call them integer flows. Perhaps surprisingly, Exercise 13.2 is not true when the edge capacities of G are allowed to be arbitrary real numbers. This is not such bad news, however: it simply says that there exists a sufficiently foolish way of choosing augmenting paths so that F ORD –F ULKERSON never terminates. If we use a reasonably good heuristic (such as the shortest-path heuristic used in the Edmonds–Karp algorithm of §13.1.3), termination is guaranteed, and the running time needn’t depend on | f ∗ |. 13.1.3 The Edmonds–Karp Algorithm The Edmonds–Karp algorithm is an implementation of the Ford–Fulkerson algorithm in which the the augmenting path p is chosen to have minimal length among all possible augmenting paths (where each edge is assigned length 1, regardless of its capacity). Thus the Edmonds–Karp algorithm can be implemented by using a breadth-first search in line 5 of the pseudocode for F ORD –F ULKERSON. Proposition 13.4 (CLRS Theorem 26.8). In the Edmonds–Karp algorithm, the total number of aug¡ ¢ mentations is O(V E). Thus total running time is O V E 2 . Proof sketch. • First one can show that the lengths of the paths p found by breadth-first search in line 5 of F ORD –F ULKERSON are monotonically nondecreasing (this is Lemma 26.7 of CLRS). Lec 13 – pg. 6 of 11 • Next, one can show that each edge e ∈ E can only be the bottleneck for p at most O(V ) times. (By “bottleneck,” we mean that e is the (or, an) edge of smallest capacity in p, so that c f (p) = c f (e).) • Finally, because only O(E) pairs of vertices can ever be edges in G f and because each edge can only be the bottleneck O(V ) times, it follows that the number of augmenting paths p used in the Edmonds–Karp algorithm is at most O(V E). • Again, since each iteration of lines 5–13 of F ORD –F ULKERSON (including the breadth-first ¡ ¢ search) takes time O(E), the total running time for the Edmonds–Karp algorithm is O V E 2 . The shortest-path heuristic of the Edmonds–Karp algorithm is just one possibility. Another in¡ ¢ teresting heuristic is relabel-to-front, which gives a running time of O V 3 . We won’t expect you to know the details of relabel-to-front for 6.046, but you might find it interesting to research other heuristics on your own. 13.2 The Max Flow–Min Cut Equivalence Definition. A cut (S, T = V \ S) of a flow network G is just like a cut (S, T) of the graph G in the sense of §3.3, except that we require s ∈ S and t ∈ T. Thus, any path from s to t must cross the cut (S, T). Given a flow f in G, the net flow f (S, T) across the cut (S, T) is defined as f (S, T) = X X f (u, v) − u ∈ S v∈ T X X f (v, u). (13.4) u ∈ S v∈ T One way to picture this is to think of the cut (S, T) as an oriented dam in which we count water flowing from S to T as positive and water flowing from T to S as negative. The capacity of the cut (S, T) is defined as X X c(u, v). (13.5) c(S, T) = u ∈ S v∈ T The motivation for this definition is that c(S, T) should represent the maximum amount of water that could ever possibly flow across the cut (S, T). This is explained further in Proposition 13.6. Lemma 13.5 (CLRS Lemma 26.4). Given a flow f and a cut (S, T), we have f (S, T) = | f | . We omit the proof, which can be found in CLRS. Intuitively, this lemma is an easy consequence of flow conservation. The water leaving s cannot build up at any of the vertices in S, so it must cross over the cut (S, T) and eventually pour out into t. Proposition 13.6. Given a flow f and a cut (S, T), we have f (S, T) ≤ c(S, T). Thus, applying Lemma 13.5, we find that for any flow f and any cut (S, T), we have | f | ≤ c(S, T). Lec 13 – pg. 7 of 11 Proof. In (13.4), f (v, u) is always nonnegative. Moreover, we always have f (u, v) ≤ c(u, v) by the capacity constraint. The conclusion follows. Proposition 13.6 tells us that the magnitude of a maximum flow is at most equal to the capacity of a minimum cut (i.e., a cut with minimum capacity). In fact, this bound is tight: Theorem 13.7 (Max Flow–Min Cut Equivalence). Given a flow network G and a flow f , the following are equivalent: (i) f is a maximum flow in G. (ii) The residual network G f contains no augmenting paths. (iii) | f | = c(S, T) for some cut (S, T) of G. If one (and therefore all) of the above conditions hold, then (S, T) is a minimum cut. Proof. Obviously (i) implies (ii), since an augmenting path in G f would give us a way to increase the magnitude of f . Also, (iii) implies (i) because no flow can have magnitude greater than c(S, T) by Proposition 13.6. Finally, suppose (ii). Let S be the set of vertices u such that there exists a path s u in G f . Since there are no augmenting paths, S does not contain t. Thus (S, T) is a cut of G, where T = V \ S. Moreover, for any u ∈ S and any v ∈ T, the residual capacity c f (u, v) must be zero (otherwise the path s u in G f could be extended to a path s u → v in G f ). Thus, glancing back at (13.1), we find that whenever u ∈ S and v ∈ T, we have   if (u, v) ∈ E   c(u, v) f (u, v) = 0 if (v, u) ∈ E   0 (but who cares) otherwise. Thus we have f (S, T) = X X u ∈ S v∈ T c(u, v) − X X 0 = c(S, T) − 0 = c(S, T); u ∈ S v∈ T so (iii) holds. Because the magnitude of any flow is at most the capacity of any cut, f must be a maximum flow and (S, T) must be a minimum cut. Corollary 13.8. The Ford–Fulkerson algorithm is correct. Proof. When F ORD –F ULKERSON terminates, there are no augmenting paths in the residual network Gf . 13.3 Generalizations The definition of a flow network that we laid out may seem insufficient for handling the types of flow problems that come up in practice. For example, we may want to find the maximum flow in a directed graph which sometimes contains both an edge (u, v) and its reversal (v, u). Or, we might want to find the maximum flow in a directed graph with multiple sources and sinks. It turns out that both of these generalizations can easily be reduced to the original problem by performing clever graph transformations. Lec 13 – pg. 8 of 11 u u 3 5 3 w 5 3 v v Figure 13.3. We can resolve the issue of E containing both an edge and its reversal by creating a new vertex and rerouting one of the old edges through that vertex. 13.3.1 Allowing both an edge and its reversal Suppose we have a directed weighted graph G = (V , E) with distinguished vertices s and t. We would like to use the Ford–Fulkerson algorithm to solve the flow problem on G, but G might not be a flow network, as E might contain both (u, v) and (v, u) for some pair of vertices u, v. The trick is to construct a new graph G 0 = (V 0 , E 0 ) from G in the following way: Start with (V 0 , E 0 ) = (V , E). For every unordered pair of vertices { u, v} ⊆ V such that both (u, v) and (v, u) are in E, add a dummy vertex w to V 0 . In E 0 , replace the edge (u, v) with edges (u, w) and (w, v), each with capacity c(u, v) (see Figure 13.3). It is easy to see that solving the flow problem on G 0 is equivalent to solving the flow problem on G. But G 0 is a flow network, so we can use F ORD –F ULKERSON to solve the flow problem on G 0 . 13.3.2 Allowing multiple sources and sinks Next suppose we have a directed graph G = (V , E) in which there are multiple sources s 1 , . . . , s k and multiple sinks t 1 , . . . , t ` . Again, it makes sense to talk about the flow problem in G, but the Ford– Fulkerson algorithm does not immediately give us a way to solve the flow problem in G. The trick this time is to add new vertices s and t to V . Then, join s to each of s 1 , . . . , s k with a directed edge of capacity ∞,5 and join each of t 1 , . . . , t ` to t with a directed edge of capacity ∞ (see Figure 13.4). Again, it is easy to see that solving the flow problem in this new graph is equivalent to solving the flow problem in G. 13.3.3 Multi-commodity flow Even more generally, we might want to transport multiple types of commodities through our network simultaneously. For example, perhaps G is a road map of New Orleans and the commodities are emergency relief supplies (food, clothing, flashlights, gasoline. . . ) in the wake of Hurricane Katrina. In the multi-commodity flow problem, there are commodities 1, . . . , k, sources s 1 , . . . , s k , sinks t 1 , . . . , t k , and quotas (i.e., positive numbers) d 1 , . . . , d k . Each source s i needs to send d i units of commodity i to sink t i . (See Figure 13.5.) The problem is to determine whether there is a way to do so while still obeying flow conservation and the capacity constraint, and if so, what that way is. 5 The symbol ∞ plays the role of a sentinel value representing infinity (such that ∞ > x for every real number x). Depending on your programming language (and on whether you cast the edge capacities as integers or floating-point numbers), the symbol ∞ may or may not be supported natively. If it is not supported natively, you will have to either implement it or add extra code to the implementation of F ORD –F ULKERSON so that operations on edge capacities support Lec 13 – pg. 9 of 11 s1 t1 ∞ s2 ∞ ∞ ∞ s t2 ∞ ∞ t ∞ s3 t3 s4 Figure 13.4. We can allow multiple sources and sinks by adding a “master” source that connects to each other source via an edge of capacity ∞, and similarly for the sinks. s1 t1 = t2 s2 t3 s3 Figure 13.5. An instance of the multi-commodity flow problem with three commodities. Lec 13 – pg. 10 of 11 It turns out that the multi-commodity flow problem is NP-complete, even when k = 2 and all the edge capacities are 1. Thus, most computer scientists currently believe that there is no way to solve the multi-commodity flow problem in polynomial time, though it has not been definitively proved yet. both numbers and the symbol ∞. Lec 13 – pg. 11 of 11