Understanding Max Flow and Min Cut Networks

CSE 421 Winter 2025 Lecture 16: Max Flow Min Cut Nathan Brunelle http://www.cs.uw.edu/421

Flow Network Flow network: Abstraction for material flowing through the edges. ? = (?,?) directed graph, no parallel edges. Two distinguished nodes: ? = source, ? = sink. ?(?) = capacity of edge ? 0. 9 a d 10 10 15 15 4 5 8 10 source sink s b e t 15 4 6 10 15 capacity 30 c f 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 3

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 ?, ? ? = 9 a d 10 4/10 15 ? ? 15 4/4 ? out of ? 5 4/8 4/10 s b e t Only show non-zero values of ? 15 4 6 10 15 value = 4 30 c f 4

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 ?, ? ? = 6/9 a d 6/10 10/10 15 ? ? 15 4/4 ? out of ? 3/5 8/8 8/10 s b e t Only show non-zero values of ? 15 4 1/6 11/15 10/10 value = 24 11/30 c f 5

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 6

Towards a Max Flow Algorithm What about the following greedy algorithm? Start with ?(?) = ? for all edges ? ?. While there is an ?-? path ? where each edge has ? ? < ?(?). Augment flow along ?; that is: Let ? = min ? ?(? ? ? ? ) Add ? to flow on every edge ? along path ?. (Adds ? to ?(?).) Can get stuck... u u Has flow value 20 and no path? 10/10 20/20 10 20/20 10/30 t s 20/30 t s 20/20 10/10 20/20 10 but 30 is possible v v 7

Another Stuck Example On every ?-? path there is some edge with ? ? = ?(?): 6/9 a d Value of flow = 24 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 11/30 c f Next idea: Ford-Fulkerson Algorithm, which applies greedy ideas to a residual graph that lets us reverse prior flow decisions from the basic greedy approach to get optimal results! 8

Greed Revisited: Residual Graph & Augmenting Paths The only way we could route more flow from s to t would be to reduce the flow from u to v to make room for that amount of extra flow from s to v. But to conserve flow we also would need to increase the flow from u to t by that same amount. u 10 20/20 20/30 t s 20/20 10 v u Suppose that we took this flow ? as a baseline, what changes could each edge handle? We could add up to 10 units along sv or ut or uv We could reduce by up to 20 units from su or uv or vt This gives us a residual graph ?? of possible changes where we draw reducing as sending back . 20 10 2010 t s 20 10 v 9

Greed Revisited: Residual Graph & Augmenting Paths Augment flow along path u u 10/10 10 20/20 20/20 20/30 10/30 t t s s 20/20 20/20 10 10/10 v v Residual graph ?? u Path in ?? u 20 10 20 10 2010 2010 t s t s 20 10 20 10 v v 10

Greed Revisited: Residual Graph & Augmenting Paths u 10/10 20/20 10/30 t s 20/20 10/10 v New residual graph ?? u 20 10 No path can even leave ?! 1020 t s 20 10 v 11

Residual Graphs An alternative way to represent a flow network Represents the net available flow between two nodes 6/17 u v Original edge: ? = ?,? ?. Flow ?(?), capacity ?(?). residual capacity 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? 11 6 u v residual capacity Residual graph: ??= (?,??). Residual edges with residual capacity ??? > ?. ??= ? ? ? < ? ? {?R: ? ? > ?}. 12

Residual Graphs and Augmenting Paths residual capacity 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? 11 6 u v residual capacity Residual graph: ??= (?,??). Residual edges with residual capacity ??? > ?. ??= ? ? ? < ? ? {?R: ? ? > ?}. Augmenting Path: Any ?-? path ? in ??. Let bottleneck(?)= min ? ? ??(?). Ford-Fulkerson idea:Repeat find an augmenting path ? and increase flow by bottleneck(?) until none left. 13 13

Ford-Fulkerson Algorithm a b 4 capacity ?: 6 8 10 10 2 10 10 s c d t 9 14

Ford-Fulkerson Algorithm 0 flows not shown a b 4 capacity ?: 6 8 10 10 2 Flow value = 0 10 10 s c d t 9 a b 4 residual capacity ??: 6 8 10 10 2 10 10 s c d t 9 15

Ford-Fulkerson Algorithm 0 flows not shown a b 4 capacity ?: 6 10 8/ 10 2 Flow value = 0 8/ 8 +8=8 10 8/ 10 s c d t 9 a b 4 residual capacity ??: 6 8 10 10 2 10 10 s c d t 9 16

Ford-Fulkerson Algorithm a b 4 ?: 6 8/8 10 8/10 2 Flow value = 8 10 8/10 s c d t 9 4 a b 8 ??: 6 8 10 2 2 2 8 10 9 s c d t 17

Ford-Fulkerson Algorithm a b 4 +2=10 ?: 6 8/8 10 8/10 2 2/ Flow value = 8 +2=10 10 8/10 +2=10 s c d t 2/ 9 4 a b 8 ??: 6 8 10 2 2 2 8 10 9 s c d t 18

Ford-Fulkerson Algorithm a b 4 ?: 6 8/8 10 10/10 2/2 Flow value = 10 10 10/10 s c d t 2/9 4 a b ??: 6 8 10 10 2 10 10 7 2 s c d t 19

Ford-Fulkerson Algorithm a b 4 ?: 6 6/ 8/8 6/ 10 10/10 2/2 Flow value = 10 +6=16 6/ 10 10/10 s c d t 2/9 +6=8 4 a b ??: 6 8 10 10 2 10 10 7 2 s c d t 20

Ford-Fulkerson Algorithm a b 4 ?: 6/6 8/8 6/10 10/10 2/2 Flow value = 16 10/10 s c d t 6/10 8/9 4 a b 6 ??: 6 8 4 10 2 10 4 6 1 8 s c d t 21

Ford-Fulkerson Algorithm a b 4 2/ ?: 6/6 8/8 6/10 +2=8 10/10 2/2 Flow value = 16 -2=0 +2=18 10/10 s c d t 6/10 +2=8 8/9 4 a b 6 ??: 6 8 4 10 2 10 1 8 4 6 s c d t 22

Ford-Fulkerson Algorithm a b 2/4 ?: 6/6 8/8 8/10 10/10 2 Flow value = 18 8/10 10/10 s c d t 8/9 2 2 a b 8 ??: 6 8 2 10 2 1 8 2 8 10 s c d t 23

Ford-Fulkerson Algorithm +1=3 a b 2/4 ?: 6/6 8/8 -1=7 8/10 +1=9 10/10 2 Flow value = 18 +1=19 8/10 +1=9 10/10 s c d t 8/9 +1=9 2 2 a b 8 ??: 6 8 2 10 2 1 8 2 8 10 s c d t 24

Ford-Fulkerson Algorithm a b 3/4 ?: 6/6 7/8 9/10 10/10 2 Flow value = 19 9/10 10/10 s c d t 9/9 3 1 a b 9 ??: 1 6 7 1 10 2 9 1 9 10 s c d t 25

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 27

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

Minimum Cut Problem Minimum s-t cut problem: Given: a flow network Find: an ?-? cut of minimum capacity 9 a d capacity 28 10 10 15 15 4 5 10 8 source sink s b e t ? 15 4 6 10 15 30 c f 29

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

Certificate of Optimality Let ? be any ?-? flow and (?,?) be any ?-? cut. If ? ? = ?(?,?) then ? is a max flow and (?,?) is a min cut. 9/9 a d Value of flow = 28 9/10 10/10 15 1/15 4 Capacity of cut = 28 4/5 8/8 9/10 s ? b e t 15 4 4/6 Both are optimal! Each certified correctness of the other! 14/15 10/10 14/30 c f 31 31

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 32

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 33

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

Weak Duality - Idea 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 35

Weak Duality - Proof 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 ? = ? ?,? 36

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 38 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 39 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 40

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 41 residual graph