Max Flow: Theory, Definitions, and Applications

cse 421 winter 2025 lecture 17 max flow running n.w
1 / 28
Embed
Share

Explore the world of maximum flow networks through definitions, the Ford-Fulkerson algorithm, residual graphs, augmenting paths, cuts, and their significance in solving the maximum flow problem. Understand how flows and cuts are interconnected and form the basis of various graph problems.

  • Max Flow
  • Network Flows
  • Graph Theory
  • Optimization

Uploaded on | 0 Views


Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript


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

  2. 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

  3. 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

  4. 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

  5. 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

  6. 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

  7. 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

  8. 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

  9. 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

  10. 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

  11. 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

  12. 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

  13. 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

  14. 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

  15. 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

  16. 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

  17. 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

  18. 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 ? }

  19. 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

  20. 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

  21. 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

  22. 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

  23. 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

  24. 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

  25. 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

  26. 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

  27. 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

  28. 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)

More Related Content