Max Flow: Theory, Definitions, and Applications

CSE 421 Winter 2025 Lecture 17: Max Flow Running Time Nathan Brunelle http://www.cs.uw.edu/421

Flows Defn: An ?-? flow in a flow network is a function ?: ? that satisfies: For each ? ?: ? ? ? ?(?) [capacity constraints] For each ? ? {?,?} : [flow conservation] ? ? = ?(?) ? into ? ? out of ? Defn: The value of flow ?, 0/9 a d 0/10 4/10 0/15 ? ? = ? ? 0/15 4/4 ? out of ? 0/5 4/8 4/10 s b e t 0/15 0/4 0/6 0/10 0/15 value = 4 0/30 c f 2

Maximum Flow Problem Given: a flow network Find: an ?-? flow of maximum value 6/9 a d 6/10 10/10 15 15 4/4 3/5 8/8 8/10 s b e t 15 4 1/6 11/15 10/10 value = 24 11/30 c f 3

Residual Graphs and Augmenting Paths Residual edges of two kinds: Forward: ? = (?,?) with capacity ??? = ? ? ? ? Amount of extra flow we can add along? Backward: ?R = (?,?) with capacity ??? = ? ? Amount we can reduce/undo flow along? 6/17 u v residual capacity Residual graph: ??= (?,??). Residual edges with residual capacity ??? > ?. ??= ? ? ? < ? ? 11 6 u v {?R: ? ? > ?}. residual capacity Augmenting Path: Any ?-? path ? in ??. Let bottleneck(?)= min ? ? ??(?). Ford-Fulkerson idea:Repeat find an augmenting path ? and increase flow by bottleneck(?) until none left. 4 4

Cuts Defn: An ?-? cut is a partition (?,?) of ? with ? ? and ? ?. The capacity of cut (?,?) is ? ?,? = ?(?) ? out of ? 9 a d capacity 30 10 10 15 15 4 8 10 5 source sink s b e t 15 ? 4 6 10 15 30 c f 5

Minimum Cut Problem Defn: An ?-? cut is a partition (?,?) of ? with ? ? and ? ?. The capacity of cut (?,?) is ? ?,? = ?(?) ? out of ? Minimum s-t cut problem: Given: a flow network Find: an ?-? cut of minimum capacity 9 a d 10 10 15 15 4 5 10 8 source sink s b e t ? 15 4 6 10 15 capacity 28 30 c f 6

Flows and Cuts Let ? be any ?-? flow and (?,?) be any ?-? cut: Flow Value Lemma: The net value of the flow sent across (?,?) equals ? ? . Intuition: All flow coming from ? must eventually reach ?, and so must cross that cut Weak Duality: The value of the flow is at most the capacity of the cut; i.e., ? ? ? ?,? . Intuition: Since all flow must cross any cut, any cut s capacity is an upper bound on the flow Corollary: If ? ? = ?(?,?) then ? is a maximum flow and (?,?) is a minimum cut. Intuition: If we find a cut whose capacity matches the flow, we can t push more flow through that cut because it s already at capacity. We additionally can t find a smaller cut, since that flow was achievable. 7

Max-Flow Min-Cut Theorem Augmenting Path Theorem: Flow ? is a max flow there are no augmenting paths wrt ? Max-Flow Min-Cut Theorem: The value of the max flow equals the value of the min cut. [Elias-Feinstein-Shannon 1956, Ford-Fulkerson 1956] Maxflow = Mincut Proof:We prove both together by showing that all of these are equivalent: (i) There is a cut (?,?) such that ?(?) = ?(?,?). (ii) Flow ? is a max flow. (iii) There is no augmenting path w.r.t. ?. (i) (ii): Comes from weak duality lemma. (ii) (iii): (by contradiction) If there is an augmenting path w.r.t. flow ? then we can improve ?. Therefore ? is not a max flow. (iii) (i): We will use the residual graph to identify a cut whose capacity matches the flow 8

Flow Value Lemma Idea Flow Value Lemma: Let ? be any ?-? flow and (?,?) be any ?-? cut. The net value of the flow sent across the cut equals ?(?): ? ? ? ? = ?(?) ? out of ? ? into ? Why is it true? Add vertices to ? side one by one. By flow conservation, net value doesn t change 6/9 a d 6/10 10/10 15 15 4/4 3/5 8/8 8/10 s ? b e t 15 4 1/6 11/15 10/10 value = 24 11/30 = 28 - 4 c f 9

Flow Value Lemma Proof Flow Value Lemma: Let ? be any ?-? flow and (?,?) be any ?-? cut. The net value of the flow sent across the cut equals ?(?): ? ? ? ? = ?(?) ? out of ? ? into ? Proof: ? ? = ? ? = ?. No edges into ? since it is a source ? out of ? = ? ? ? ? + ? ? ? ? ? out of ? ? into ? ? out of ? ? into ? ? ? ? = ? ? ? ? ? out of ? ? into ? = ? by flow conservation. Contributions from internal edges of ? cancel. 10

Weak Duality - Idea (i) (ii) Weak Duality: Let ? be any ?-? flow and (?,?) be any ?-? cut. The value of the flow is at most the capacity of the cut; i.e., ? ? ?(?,?): 6/9 a d Value of flow = 24 = 28 - 4 6/10 10/10 15 15 4/4 Capacity of cut = 28 3/5 8/8 8/10 s ? b e t 15 4 1/6 11/15 10/10 11/30 c f 11

Weak Duality - Proof (i) (ii) Weak Duality: Let ? be any ?-? flow and (?,?) be any ?-? cut. The value of the flow is at most the capacity of the cut; i.e., ? ? ? ?,? . ? ? = ? ? ? ? Proof: ? out of ? ? into ? ? ? since ? ? ? ? out of ? since ? ? ?(?) ? ? ? out of ? = ? ?,? 12

Proof of Max-Flow Min-Cut Theorem (iii) (i): Claim: If there is no augmenting path w.r.t. ?, there is a cut (?,?) s.t. ?(?) = ?(?,?). Proof of Claim: Let ? be a flow with no augmenting paths. Let ? be the set of vertices reachable from ? in residual graph ??. By definition of ?, ? ?. Since no augmenting path (?-? path in ??), ? ?. A B t s original network A B t s residual graph

Proof: Identifying the Min Cut (iii) (i): Claim: If there is no augmenting path w.r.t. ?, there is a cut (?,?) s.t. ?(?) = ?(?,?). Proof of Claim: Let ? be a flow with no augmenting paths. Let ? be the set of vertices reachable from ? in residual graph ??. By definition of ?, ? ?. Since no augmenting path (?-? path in ??), ? ?. A B t s Then ? ? = ? ? ? ? (by Flow-Value Lemma) original network ? out of ? ? into ? A B t s 14 residual graph

Identifying the Min Cut: No Inflow (iii) (i): ?(?) = ? Claim: If there is no augmenting path w.r.t. ?, there is a cut (?,?) s.t. ?(?) = ?(?,?). A B ? x Proof of Claim: Let ? be a flow with no augmenting paths. Let ? be the set of vertices reachable from ? in residual graph ??. By definition of ?, ? ?. Since no augmenting path (?-? path in ??), ? ?. y t s Then original network ? ? = ? ? ? ? ??can t exist because then ? would be reachable from ? ? out of ? ? into ? = ? ? (By contradiction: If an edge going into ? had flow then the backward edge would be in the residual graph, so the edge should not cross the cut) ?R A B ? out of ? x y t s 15 residual graph

Identifying the Min Cut: Saturated Outflow (iii) (i): ?is saturated No unused capacity on? ? ? = ?(?) A Claim: If there is no augmenting path w.r.t. ?, there is a cut (?,?) s.t. ?(?) = ?(?,?). B Proof of Claim: Let ? be a flow with no augmenting paths. Let ? be the set of vertices reachable from ? in residual graph ??. By definition of ?, ? ?. Since no augmenting path (?-? path in ??), ? ?. t s ? Then ? ? = ? ? ? ? original network ??can t exist because then ? would be reachable from ? ? out of ? ? into ? = ? ? A B ? out of ? t (By contradiction: If an edge going out of ? had unused capacity then the forward edge would be in the residual graph, so the edge should not cross the cut) = ? ? ? out of ? ? s y residual graph 16

Identifying the Min Cut: Conclusion (iii) (i): Claim: If there is no augmenting path w.r.t. ?, there is a cut (?,?) s.t. ?(?) = ?(?,?). Proof of Claim: Let ? be a flow with no augmenting paths. Let ? be the set of vertices reachable from ? in residual graph ??. By definition of ?, ? ?. Since no augmenting path (?-? path in ??), ? ?. A B t Then s ? ? = ? ? ? ? ? out of ? ? into ? original network = ? ? A B ? out of ? t = ? ? = ?(?,?) (by Definition) ? out of ? s 17 residual graph

Fork Fulkerson Algorithm FordFulkerson(G, s, t, c){ for each ? ?{ set ? ? = 0 } calculate residual graph ?? while ?? has an ? ? path ?{ augment(?,?,?) update ?? } return ? } augment(?,?,?){ ? = bottleneck(?) for each ? ?{ ? ? += ? ? ?? = ? } return ? }

MaxFlow/MinCut & Ford-Fulkerson Algorithm Augmenting Path Theorem: Flow ? is a max flow there are no augmenting paths wrt ? Max-Flow Min-Cut Theorem: The value of the max flow equals the value of the min cut. [Elias-Feinstein-Shannon 1956, Ford-Fulkerson 1956] MaxFlow = MinCut Flow Integrality Theorem: If all capacities are integers then there is a maximum flow with all-integer flow values. Ford-Fulkerson Algorithm: ?(?) per iteration. With integer capacities each at most ? need at most MaxFlow < ?? iterations for a total of ? ??? time. 19 19

Ford-Fulkerson Efficiency Worst case runtime ? ??? with integer capacities ?. ?(?) time per iteration. At most ?? iterations. This is pseudo-polynomial running time. May take exponential time, even with integer capacities: c = ???, say 1 1 1 a a a c-1 c-1 c c c-1 c etc. s t s t s t 1 1 1 c c-1 c c c-1 1 c-1 1 b b 1 b ??= ? 20

Polynomial-Time Variant of Ford-Fulkerson Use care when selecting augmenting paths. Some choices lead to exponential algorithms. Clever choices lead to polynomial algorithms. If capacities are irrational, algorithm not guaranteed to terminate! Goal: Choose augmenting paths so that: Can find augmenting paths efficiently. Few iterations. Choose augmenting paths with fewest number of edges. [Edmonds-Karp 1972 , Dinitz 1970] Just run BFS to find an augmenting path! 21

Edmonds-Karp Algorithm (Ford-Fulkerson with BFS) Use Breadth First Search as the search algorithm to find an ?-? path in ??. Using any shortest augmenting path Theorem: Ford-Fulkerson using BFS terminates in ?(???) time. [Edmonds-Karp, Dinitz] One of the most obvious ways to implement Ford-Fulkerson is always polynomial time Why might this be good intuitively? Longer augmenting paths involve more edges so may be more likely to hit a low residual capacity one which would limit the amount of flow improvement. The proof uses a completely different idea 22

Edmonds-Karp Algorithm (Ford-Fulkerson with BFS) Analysis Focus: For any edge ? that could be in the residual graph ??, (either an edge in ? or its reverse) count # of iterations that ? is the first bottleneck edge on the augmenting path chosen by the algorithm. Claim:This can t happen in more than ?/? iterations. Proof: Write ? = (?,?). Show that each time it happens,the distance from ? to ? in the residual graph ?? is at least ? more than it was the last time. This would be enough since the distance is < ? (or infinite and hence ?isn t reachable) so this can happen at most ?/? times. 23

Distances in the Residual Graph Key Lemma: Let ? be a flow, ?? the residual graph, and ? be a shortest augmenting path. No vertex is closer to ? in the residual graph after augmenting along ?. Proof: Augmenting along ? can only change the edges in ?? by either: 1. Deleting a forward edge Deleting any edge can never reduce distances 2. Add a backward edge (?,?) that is the reverse of an edge (?,?) of ? Since ? was a shortest path in ??, the distance from ? to ? in ?? is already more than the distance from ? to ?. Using the new backward edge (?,?) to get to ? would be an even longer path to ?so it is never on a shortest path to any node in the new residual graph. 24

Augmentation vs BFS ?: ?? : ??: ?: s s s s 5/9 8/9 4 1 5 8 x x x x 3/10 6/10 3 6 7 4 u u u u edge deleted 3 3/3 3 3 v v v v 3 2/5 5/5 2 5 t t t t 25

First Bottleneck Edges in ?? Shortest ?-? path ? in ?? Write ??= bottleneck(?) > ?? ?? ?? > ?? t x w s u v ??(?,?) = ??(?,?) + ? since ? is a shortest path. After augmenting along ?, edge (?,?) disappears; but will have edge (?,?) distance is ? larger than before t x w s u v For (?,?) to be a first bottleneck edge later, it must get added back to the residual graph by augmenting along a shortest path ? containing (?,?) in ?? for some flow ? Since ? is shortest ?? ?,? = ?? ?,? + ? ???,? + ? = ??(?,?) + ? The next time that (?,?) is first bottleneck edge is even later so distance is at least as large! 26

Edmonds-Karp Algorithm (Ford-Fulkerson with BFS) Analysis Focus: For any edge ? that could be in the residual graph ??, (either an edge in ? or its reverse) count # of iterations that ? is the first bottleneck edge on the augmenting path chosen by the algorithm. Claim:This can t happen in more than ?/? iterations Claim Theorem: Only ?? edges and ?(?) time per iteration so ?(???) time overall. 27

History & State of the Art for MaxFlow Algorithms bound ? ?? 21 2013 Orlin ? ? log? 1? log ? 22 2014 Lee & Sidford ???/???/? log? 1? 23 2016 Madry ??/? ?/???log? 1?log ? 24 2021 Gao, Liu, & Peng ??/? ?/??log? 1?log ? 25 2022 van den Brand et al. ??+? ?log? 26 2022 Chen et al. Tables use ? instead of ? for the upper bound on capacities Methods: Augmenting Paths increase flow to capacity Preflow-Push decrease flow to get flow conservation Linear Programming randomized, high probability of optimality Source: Goldberg & Rao, FOCS 97 28 2012 Orlin + King et al. O(nm)