Lecture 15: Graph Algorithms - MAX-Flow CP312 PDF

CP312 Algorithm Design and Analysis I LECTURE 15: GRAPH ALGORITHMS – MAX-FLOW Flow networks model material flowing through a transportation network Flow Networks Def: A flow network is a directed weighted graph 𝐺 = (𝑉, 𝐸) with: ◦ Two distinguished vertices: a source 𝑠 and a sink 𝑡. ◦ Each edge 𝑢, 𝑣...

CP312 Algorithm Design and Analysis I LECTURE 15: GRAPH ALGORITHMS – MAX-FLOW Flow networks model material flowing through a transportation network Flow Networks Def: A flow network is a directed weighted graph 𝐺 = (𝑉, 𝐸) with: ◦ Two distinguished vertices: a source 𝑠 and a sink 𝑡. ◦ Each edge 𝑢, 𝑣 ∈ 𝐸 has a non-negative capacity 𝑐(𝑢, 𝑣). If 𝑢, 𝑣 ∉ 𝐸 then 𝑐 𝑢, 𝑣 = 0. 9 𝑣1 10 𝑣4 15 4 5 𝑠 𝑣2 8 15 𝑣5 6 4 10 10 𝑡 15 15 10 𝑣3 16 𝑣6 Capacity Assume all nodes are reachable from 𝑠 Flow Networks Def: A flow on 𝐺 is a function 𝑓: 𝑉 × 𝑉 → ℝ satisfying the following: ◦ Capacity Constraint: For all 𝑢, 𝑣 ∈ 𝑉 ◦ Flow Conservation: For all 𝑢 ∈ 𝑉 − 𝑠, 𝑡 A flow should assign a value to every edge in the graph (should not exceed capacity of edge) Flow 0 ≤ 𝑓 𝑢, 𝑣 ≤ 𝑐(𝑢, 𝑣) σ𝑣∈𝑉 𝑓 𝑢, 𝑣 − σ𝑣∈𝑉 𝑓 𝑣, 𝑢 = 0 Capacity 4/10 2/3 Flow going out of 𝑢 = Flow going in 𝑢 𝑢 6/20 Def: The net flow 𝑓መ is defined as: 𝑓መ 𝑢, 𝑣 = 𝑓 𝑢, 𝑣 − 𝑓(𝑣, 𝑢) 8/10 For all vertices 𝑢 ∈ 𝑉 − {𝑠, 𝑡}: ෍ 𝑓መ 𝑢, 𝑣 = 0 𝑣∈𝑉 Flow Conservation: For all 𝑢 ∈ 𝑉 − 𝑠, 𝑡 ෍ 𝑓መ 𝑢, 𝑣 = ෍ 𝑓 𝑢, 𝑣 − ෍ 𝑓 𝑣, 𝑢 = 0 Flow Networks 𝑣∈𝑉 𝑣∈𝑉 𝑣∈𝑉 Def: The value of a flow is the total net flow out of the source: 𝑓 = σ𝑣∈𝑉 𝑓መ 𝒔, 𝑣 = σ𝑣∈𝑉 𝑓 𝒔, 𝑣 − σ𝑣∈𝑉 𝑓 𝑣, 𝒔 5/9 10/10 𝑣1 𝑣4 5/15 0/4 5/5 𝑠 𝑣2 0/4 5/8 0/15 𝑣5 0/6 5/10 10/10 0/15 10/10 10/15 𝑣3 10/16 𝑣6 𝑡 |𝑓| = 5 + 10 + 10 = 25 Maximum Flow (Max-flow) Problem: Find a flow with maximum value in a weighted directed graph. Input: A weighted connected directed graph 𝐺 = (𝑉, 𝐸). A source 𝑠 node and a sink node 𝑡. Output: A flow 𝑓 (an assignment to all edges) such that: |𝑓| = max ෍ 𝑓𝑖 𝒔, 𝑣 − ෍ 𝑓𝑖 𝑣, 𝒔 𝑓𝑖 𝑣∈𝑉 𝑣∈𝑉 Maximum Flow Example of a max-flow 𝑓: 8/9 10/10 𝑣1 𝑣4 2/15 0/4 5/5 𝑠 𝑣2 0/4 8/8 0/15 𝑣5 3/6 8/10 10/10 0/15 10/10 13/15 𝑣3 13/16 𝑣6 𝑡 |𝑓| = 8 + 10 + 10 = 28 Related Problem: Minimum Cut We want to divide the vertices into two disjoint sets separating 𝑠 and 𝑡 such that the total capacity of the edges connecting the sets is minimized. 9 10 𝑣1 𝑣4 15 4 5 𝑠 𝑣2 4 8 15 𝑣5 6 10 10 𝑡 15 15 10 𝑣3 16 𝑣6 Definitions for Minimum Cut Def: A cut 𝑇 = (𝐴, 𝐵) of a flow network 𝐺 = (𝑉, 𝐸) is a partition of the vertices into two disjoint sets, with 𝑠 in one set 𝐴 and 𝑡 in the other set 𝐵. Def: The cut capacity 𝑐 𝑇 is the sum of the capacities of the edges from 𝐴 to 𝐵. Def: The net flow across a cut 𝑓መ 𝑇 = 𝑓መ 𝐴, 𝐵 is the sum of the flows on its edges from 𝐴 to 𝐵 minus the sum of the flows on its edges from 𝐵 to 𝐴. 𝑓መ 𝐴, 𝐵 = ෍ ෍ 𝑓መ 𝑎, 𝑏 = ෍ 𝑎∈𝐴 𝑏∈𝐵 𝑎∈𝐴,𝑏∈𝐵 𝑓 𝑎, 𝑏 − ෍ 𝑎∈𝐴,𝑏∈𝐵 𝑓 𝑏, 𝑎 Minimum Cut (Min-cut) Problem: Find a cut with minimum capacity in a weighted directed graph. Input: A weighted connected directed graph 𝐺 = (𝑉, 𝐸). A source 𝑠 node and a sink node 𝑡. Output: A cut 𝑇 = 𝐴, 𝐵 such that 𝑠 ∈ 𝐴, 𝑡 ∈ 𝐵 and: 𝑐(𝑇) = min 𝑇𝑖 ෍ 𝑢∈𝐴𝑖 ,𝑣∈𝐵𝑖 𝑐 𝑢, 𝑣 Minimum Cut Example of a cut: 9 10 𝑣1 𝑣4 15 4 5 𝑠 𝑣2 4 8 15 𝑣5 6 10 10 𝑡 15 15 10 𝑣3 16 𝑣6 Minimum Cut Example of a cut 𝑇1 : Cut Capacity of 𝑇1 𝑐 𝑇1 = 10 + 8 + 16 = 34 9 10 𝑣1 𝑣4 15 4 5 𝑠 𝑣2 4 8 15 𝑣5 6 10 10 𝑡 15 15 10 𝑣3 𝐴 16 𝑣6 Don’t count the edges from nodes in 𝐵 to nodes in 𝐴 Minimum Cut Example of a cut: 9 10 𝑣1 𝑣4 15 4 5 𝑠 𝑣2 4 8 15 𝑣5 6 10 10 𝑡 15 15 10 𝑣3 16 𝑣6 Minimum Cut Example of a cut 𝑇2 : Cut Capacity of 𝑇2 𝑐 𝑇2 = 10 + 8 + 10 = 28 9 10 𝑣1 𝑣4 15 4 5 𝑠 𝑣2 4 8 15 𝑣5 6 10 10 𝑡 15 15 10 𝑣3 𝐴 16 𝑣6 Better than cut 𝑇1 but is it the minimum cut? Yes, 𝑇2 is the min-cut. Net flow across cut 𝑇 = (𝐴, 𝐵): 𝑓መ 𝐴, 𝐵 = Min-Cut and Max-Flow ෍ 𝑓 𝑎, 𝑏 − 𝑎∈𝐴,𝑏∈𝐵 ෍ 𝑓 𝑏, 𝑎 𝑎∈𝐴,𝑏∈𝐵 What is the relationship between a flow and a cut? Cut 𝑇1 Value of flow 𝑓 |𝑓| = 5 + 10 + 10 = 25 5/9 10/10 𝑣1 𝑣4 5/15 0/4 5/5 𝑠 5/8 𝑣2 0/15 𝑣5 0/6 0/4 5/10 10/10 𝑡 0/15 Net flow across cut 𝑇1 𝑓መ 𝑇1 = 5 + 10 + 10 = 25 10/10 10/15 𝑣3 10/16 𝐴 Cut Capacity of 𝑇1 𝑐 𝑇1 = 10 + 10 + 10 = 30 𝑣6 𝐵 Net flow across cut 𝑇 = (𝐴, 𝐵): 𝑓መ 𝐴, 𝐵 = Min-Cut and Max-Flow ෍ 𝑓 𝑎, 𝑏 − 𝑎∈𝐴,𝑏∈𝐵 ෍ 𝑓 𝑏, 𝑎 𝑎∈𝐴,𝑏∈𝐵 What is the relationship between a flow and a cut? Cut 𝑇2 Value of flow 𝑓 |𝑓| = 5 + 10 + 10 = 25 5/9 10/10 𝑣1 𝑣4 5/15 0/4 5/5 𝑠 𝑣2 0/4 5/8 0/15 𝑣5 0/6 5/10 10/10 0/15 𝑡 Net flow across cut 𝑇2 𝑓መ 𝑇2 = 10 + 10 + 5 + 10 + 0 + 0 − 5 + 5 + 0 + 0 = 25 10/10 10/15 𝑣3 10/16 𝑣6 Cut Capacity of 𝑇2 𝑐 𝑇2 = 64 Min-Cut and Max-Flow Theorem: For any flow 𝑓 and any cut 𝑇 = 𝐴, 𝐵 5/9 𝑓መ 𝑇 = |𝑓| 10/10 𝑣1 𝑣4 5/15 0/4 Net-flow of ANY cut = Value of flow 5/5 𝑠 5/8 𝑣2 0/15 𝑣5 0/6 0/4 5/10 10/10 𝑡 0/15 10/10 10/15 𝑣3 10/16 𝐴 𝑣6 𝐵 Min-Cut and Max-Flow Theorem: For any flow 𝑓 and any cut 𝑇 = 𝐴, 𝐵 5/9 𝑓 ≤ 𝑐(𝑇) 10/10 𝑣1 𝑣4 5/15 0/4 Value of ANY flow ≤ Capacity of ANY cut 5/5 𝑠 5/8 𝑣2 0/15 𝑣5 0/6 0/4 5/10 10/10 𝑡 0/15 10/10 10/15 𝑣3 10/16 𝐴 𝑣6 𝐵 Min-Cut and Max-Flow Main Theorem: 𝑓 is a maximum flow if and only if 𝑓 = 𝑐(𝑇 ∗ ) for some cut 𝑇 ∗. Max-flow = Min-cut 8/9 10/10 𝑣1 𝑣4 2/15 0/4 Corollary: Since 𝑓 ≤ 𝑐(𝑇) for any 𝑇, it must be that 𝑇 ∗ is the minimum cut. 5/5 𝑠 8/8 𝑣2 0/15 𝑣5 3/6 0/4 8/10 10/10 𝑡 0/15 10/10 13/15 𝑣3 13/16 𝐴 𝑣6 𝐵 Min-Cut and Max-Flow Corollary: Max-flow = Min-cut Max-flow = Min-cut 8/9 So it suffices to find the max-flow 10/10 𝑣4 2/15 0/4 5/5 𝑠 Let us start with some definitions and useful properties first. 𝑣1 8/8 𝑣2 0/15 𝑣5 3/6 0/4 8/10 10/10 𝑡 0/15 10/10 13/15 𝑣3 13/16 𝑣6 𝐴 𝐵 19 Property 1: Flow Cancellation Without loss of generality, positive flow goes either from 𝑢 to 𝑣, or from 𝑣 to 𝑢, but not both. 𝑓መ 𝑢, 𝑣 = 1 𝑓መ 𝑢, 𝑣 = 1 2/3 1/3 𝑣 𝑢 1/2 𝑣 𝑢 Net flow from 𝑢 to 𝑣 in both cases is 1 0/2 The capacity constraint and flow conservation are preserved by this transformation. 20 Property 2: Skew Symmetry Positive net flow from 𝑢 to 𝑣 is considered negative net flow from 𝑣 to 𝑢. 𝑓መ 𝑢, 𝑣 = 𝑓 𝑢, 𝑣 − 𝑓 𝑣, 𝑢 = 1 1/3 𝑓 𝑢, 𝑣 = 1 𝑓 𝑣, 𝑢 = 0 𝑣 𝑢 𝑓መ 𝑢, 𝑣 = −𝑓መ 𝑣, 𝑢 0/2 𝑓መ 𝑣, 𝑢 = 𝑓 𝑣, 𝑢 − 𝑓 𝑢, 𝑣 = −1 21 Residual Network Definition: Let 𝑓 be a flow on 𝐺 = (𝑉, 𝐸). The residual network 𝐺𝑓 (𝑉, 𝐸𝑓 ) is the graph with strictly positive residual capacities: መ 𝑣) 𝑐𝑓 𝑢, 𝑣 = 𝑐 𝑢, 𝑣 − 𝑓(𝑢, 𝑐𝑢 − 𝑓𝑢 𝑓𝑢 /𝑐𝑢 𝐺: 𝑣 𝑢 0/𝑐𝑣 𝐺𝑓 : Residual Capacity The residual network captures how much more flow can be admitted through some edge. 𝑣 𝑢 𝑐𝑣 + 𝑓𝑢 Residual Capacity 22 Residual Network Example: What is the residual network for this path of the graph? 3/5 𝐺: 2/6 𝑣2 𝑣1 2 𝐺𝑓 : 4 3 𝑣3 2 𝑣6 𝑣5 𝑣4 𝑣3 𝑣2 𝑣1 2/5 0/2 5/5 2/3 7 2 3 𝑣6 𝑣5 𝑣4 1 2 23 If there exists an augmenting path, it means there is a way to push more flow from 𝑠 to 𝑡 Augmenting Path Definition: Any path from 𝑠 to 𝑡 in 𝐺𝑓 is an augmenting path with respect to 𝑓. The flow can be increased along an augmenting path 𝑝 by 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 Bottleneck Capacity 𝑢,𝑣 ∈𝑝 2 𝐺𝑓 : 4 𝑣2 𝑠 3 𝑣3 2 2 7 3 𝑡 𝑣5 𝑣4 1 2 𝑐𝑓 𝑝 = 2 so the flow value can be increased by 2 24 Ford-Fulkerson Algorithm Ford-Fulkerson(𝑉, 𝐸, 𝑠, 𝑡, 𝑐): for each edge 𝑢, 𝑣 ∈ 𝐸 𝑓 𝑢, 𝑣 = 0 // Initialization while there exists an augmenting path 𝑝 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 // Use DFS to check if a path 𝑠 → 𝑡 exists in 𝐺𝑓 𝑢,𝑣 ∈𝑝 for each edge 𝑢, 𝑣 ∈ 𝑝 𝑓 𝑢, 𝑣 = 𝑓 𝑢, 𝑣 + 𝑐𝑓 (𝑝) 𝑓 𝑣, 𝑢 = 𝑓 𝑣, 𝑢 − 𝑐𝑓 (𝑝) // Update edges // Send flow along the path from 𝑠 to 𝑡 // Remove flow from the opposite path 25 Ford-Fulkerson Algorithm Initialization 0/9 𝑣1 0/10 𝑣4 0/15 0/4 0/5 𝑠 𝑣2 0/8 0/15 𝑣5 0/6 0/4 0/10 0/10 𝑡 0/15 0/10 0/15 𝑣3 0/16 𝑣6 |𝑓| = 0 26 Ford-Fulkerson Algorithm Is there an augmenting path? 𝐺𝑓 0/9 𝑣1 0/10 𝑣4 0/15 0/4 0/5 𝑠 9 𝑣2 0/8 0/10 𝑡 0/16 𝑣6 15 5 𝑠 𝑣2 8 10 15 𝑣5 6 4 0/10 𝑣3 𝑣4 4 0/15 0/15 𝑣1 10 0/15 𝑣5 0/6 0/4 0/10 10 𝑡 15 15 10 𝑣3 16 𝑣6 27 Ford-Fulkerson Algorithm Is there an augmenting path? Yes 𝐺𝑓 𝑐𝑓 (𝑝) Bottleneck Capacity 0/9 𝑣1 0/10 𝑣4 0/15 0/4 0/5 𝑠 𝑣2 0/8 𝑡 0/16 𝑣6 15 5 𝑠 0/15 𝑣2 8 10 15 𝑣5 6 4 0/10 𝑣3 𝑣4 4 0/10 0/15 𝑣1 10 0/15 𝑣5 0/6 0/4 0/10 9 10 𝑡 15 15 10 𝑣3 16 𝑣6 Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 28 Ford-Fulkerson Algorithm Update edges 𝐺𝑓 0/9 10/10 𝑣1 𝑣4 10/15 0/4 0/5 𝑠 9 𝑣2 0/8 0/15 𝑣5 0/6 0/4 𝑠 𝑣2 8 10 15 𝑣5 6 4 10 𝑡 15 15 𝑣6 Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 10 5 0/15 0/10 0/16 𝑡 𝑣4 5 4 10/10 0/15 𝑣3 𝑣1 10 0/10 10 𝑣3 16 𝑣6 |𝑓| = 10 29 Ford-Fulkerson Algorithm Is there an augmenting path? 𝐺𝑓 0/9 10/10 𝑣1 𝑣4 10/15 0/4 0/5 𝑠 9 𝑣2 0/8 0/15 𝑣5 0/6 0/4 10/10 𝑣6 10 5 𝑠 𝑣2 8 10 15 𝑣5 6 4 0/10 0/16 𝑡 𝑣4 5 4 0/15 0/15 𝑣3 𝑣1 10 0/10 10 𝑡 15 15 10 𝑣3 16 𝑣6 30 Ford-Fulkerson Algorithm Is there an augmenting path? Yes 𝐺𝑓 0/9 10/10 𝑣1 𝑣4 10/15 0/4 0/5 𝑠 9 𝑣2 0/8 0/15 𝑣5 0/6 0/4 𝑣6 10 5 𝑠 0/15 𝑣2 8 10 15 10 𝑣5 6 4 0/10 0/16 𝑡 𝑣4 5 4 10/10 0/15 𝑣3 𝑣1 10 0/10 𝑡 15 15 10 𝑣3 16 𝑣6 𝑐𝑓 (𝑝) Bottleneck Capacity Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 31 Ford-Fulkerson Algorithm Update edges 𝐺𝑓 0/9 10/10 𝑣1 𝑣4 10/15 0/4 0/5 𝑠 9 𝑣2 0/4 0/8 0/15 𝑣5 0/6 𝑡 10 0/15 𝑣6 Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 𝑣2 8 6 𝑣3 6 10 15 𝑣5 4 5 10/10 10/16 10 5 𝑠 𝑣4 5 4 10/10 10/15 𝑣3 𝑣1 10 0/10 10 𝑡 15 10 𝑣6 10 |𝑓| = 20 32 Ford-Fulkerson Algorithm Is there an augmenting path? 𝐺𝑓 0/9 10/10 𝑣1 𝑣4 10/15 0/4 0/5 𝑠 9 𝑣2 0/4 0/8 0/15 𝑣5 0/6 10/10 𝑣6 10 5 𝑠 10 10/10 10/16 𝑡 𝑣4 5 4 0/15 10/15 𝑣3 𝑣1 10 0/10 𝑣2 8 5 𝑣3 15 𝑣5 6 4 6 10 10 𝑡 15 10 𝑣6 10 33 Ford-Fulkerson Algorithm Is there an augmenting path? Yes 𝑐𝑓 𝑝 = 5 Bottleneck Capacity 0/9 10/10 𝑣1 𝑣4 10/15 0/4 0/5 𝑠 𝑣2 0/4 0/8 0/6 10/10 𝑡 10 0/15 𝑣6 10 5 𝑠 𝑣4 5 4 10/10 10/16 𝑣1 0/15 𝑣5 9 10 0/10 10/15 𝑣3 𝐺𝑓 𝑣2 8 5 𝑣3 15 𝑣5 6 4 6 10 10 𝑡 15 10 𝑣6 10 Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 34 Ford-Fulkerson Algorithm Update edges 𝐺𝑓 5/9 10/10 𝑣1 𝑣4 5/15 0/4 5/5 𝑠 5 𝑣2 0/4 5/8 0/15 𝑣5 0/6 4 10/10 𝑡 𝑠 10 10/16 𝑣6 Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 10 15 5 𝑣2 𝑣5 3 6 4 5 10/10 𝑣4 4 5 5 0/15 10/15 𝑣3 𝑣1 10 5/10 𝑣3 6 5 5 10 𝑡 15 10 𝑣6 10 |𝑓| = 25 35 Ford-Fulkerson Algorithm Is there an augmenting path? 𝐺𝑓 5/9 10/10 𝑣1 𝑣4 5/15 0/4 5/5 𝑠 5 𝑣2 0/4 5/8 0/15 𝑣5 0/6 4 10/10 𝑠 10 10/10 10/16 𝑡 𝑣6 𝑣4 4 10 5 15 5 5 0/15 10/15 𝑣3 𝑣1 10 5/10 𝑣2 𝑣5 3 6 4 5 𝑣3 6 5 5 10 𝑡 15 10 𝑣6 10 36 Ford-Fulkerson Algorithm Is there an augmenting path? Yes 𝑐𝑓 𝑝 = 3 Bottleneck Capacity 5/9 10/10 𝑣1 𝑣4 5/15 0/4 5/5 𝑠 𝑣2 0/4 5/8 0/6 4 10/10 𝑡 𝑠 10 𝑣6 𝑣4 4 10 5 15 5 5 0/15 10/10 10/16 𝑣1 0/15 𝑣5 5 10 5/10 10/15 𝑣3 𝐺𝑓 𝑣2 𝑣5 3 6 4 5 𝑣3 6 5 5 10 𝑡 15 10 𝑣6 10 Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 37 Ford-Fulkerson Algorithm Update edges 𝐺𝑓 8/9 10/10 𝑣1 𝑣4 2/15 0/4 5/5 𝑠 1 𝑣2 0/4 8/8 0/15 𝑣5 3/6 𝑡 𝑠 13 0/15 𝑣6 Update flow on the augmenting path edges for 𝐺 by 𝑐𝑓 (𝑝) 13 8 𝑣2 4 2 10/10 13/16 5 𝑣3 𝑣4 8 2 4 10/10 13/15 𝑣3 𝑣1 10 8/10 𝑣5 3 3 3 15 8 2 10 𝑡 15 10 𝑣6 13 |𝑓| = 28 38 Ford-Fulkerson Algorithm Is there an augmenting path? No 𝐺𝑓 8/9 10/10 𝑣1 𝑣4 2/15 0/4 5/5 𝑠 1 𝑣2 0/4 8/8 0/15 𝑣5 3/6 10/10 𝑡 𝑠 13 𝑣6 Max-Flow 13 8 𝑣2 4 2 10/10 13/16 5 𝑣3 𝑣4 8 2 4 0/15 13/15 𝑣3 𝑣1 10 8/10 𝑣5 3 3 3 15 8 2 10 𝑡 15 10 𝑣6 13 |𝑓| = 28 39 Ford-Fulkerson Analysis Ford-Fulkerson(𝑉, 𝐸, 𝑠, 𝑡, 𝑐): Θ(|𝐸|) Θ(|𝑉 + 𝐸|) for each edge 𝑢, 𝑣 ∈ 𝐸 𝑓 𝑢, 𝑣 = 0 // Initialization while there exists an augmenting path 𝑝 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 // Use DFS to check if a path 𝑠 → 𝑡 exists in 𝐺𝑓 𝑢,𝑣 ∈𝑝 Θ(|𝑉|) for each edge 𝑢, 𝑣 ∈ 𝑝 𝑓 𝑢, 𝑣 = 𝑓 𝑢, 𝑣 + 𝑐𝑓 (𝑝) 𝑓 𝑣, 𝑢 = 𝑓 𝑣, 𝑢 − 𝑐𝑓 (𝑝) // Update edges // Send flow along the path from 𝑠 to 𝑡 // Remove flow from the opposite path 40 Worst-Case Example 𝑣1 100 100 1 𝑠 𝑡 100 𝑣3 The while loop can take up to 200 iterations! 100 The method for choosing an augmenting path matters a lot 41 Ford-Fulkerson Analysis Assume the largest capacity is 𝑈 Ford-Fulkerson(𝑉, 𝐸, 𝑠, 𝑡, 𝑐): Θ(|𝐸|) Θ(|𝑉 + 𝐸|) 𝐸𝑈 times for each edge 𝑢, 𝑣 ∈ 𝐸 𝑓 𝑢, 𝑣 = 0 // Initialization while there exists an augmenting path 𝑝 𝑐𝑓 𝑝 = min 𝑐𝑓 𝑢, 𝑣 // Use DFS to check if a path 𝑠 → 𝑡 exists in 𝐺𝑓 𝑢,𝑣 ∈𝑝 Θ(|𝑉|) for each edge 𝑢, 𝑣 ∈ 𝑝 𝑓 𝑢, 𝑣 = 𝑓 𝑢, 𝑣 + 𝑐𝑓 (𝑝) 𝑓 𝑣, 𝑢 = 𝑓 𝑣, 𝑢 − 𝑐𝑓 (𝑝) // Update edges // Send flow along the path from 𝑠 to 𝑡 // Remove flow from the opposite path 𝑇 𝑛 = 𝐸𝑈 × ( 𝑉 + 𝐸 + 𝑉)) = 𝑂(𝐸 2 𝑈) 42 Max-Flow Applications Data mining Distributed computing Bipartite matching Network reliability/connectivity Image segmentation Multi-camera scene reconstruction Maximum multi-commodity flow … 45 Summary Know the definitions of: ◦ Max-Flow ◦ ◦ ◦ ◦ Flow and net flow across edge Value of a flow Flow Cancellation Skew Symmetry ◦ Min-Cut ◦ Cut Capacity ◦ Net flow across cut Understand the relationships between min-cut and max-flow Understand how to use Ford-Fulkerson to find the max-flow ◦ Residual Network and Augmenting Paths 55