PowerPoint Presentation
Lecture 9
Max flow, min cut
Minimum cut
Maximum flow
Max-flow min-cut theorem
Ford-Fulkerson augmenting paths algorithm
Edmonds-Karp algorithm
Bipartite matching
Maximum Flow and Minimum Cut
Two basic algorithmic problems
Important problems in combinatorial optimization
Applications / reductions
Network connectivity
Network reliability
Bipartite matching
Minimum Cut Problem
Network:
directed graph G = (V,E)
edge capacities c: V × V → R≥0
c(u,v) = 0 for (u,v) ∉ E
a source vertex s ∈ V, a sink vertex t ∈ V
Min cut problem: delete “best” set of edges to disconnect s from t
Cuts
Recall: A cut is a partition of vertices into two nonempty subsets (S, V − S)
s-t cut: cut (S, V – S) with s∈ S and t ∈ V – S
capacity(S, V – S) = sum of capacities of edges leaving S:
Minimum Cut Problem
Min-Cut Problem:
Given a network G = (V, E, s, t, c), find a s-t cut of minimum capacity.
Maximum Flow Problem
Same input as min-cut problem:
Network: directed graph G, edge capacities
c: V × V→ R≥0, source vertex s, sink vertex t
Max-Flow Problem: Assign flow to edges so as to:
Equalize inflow and outflow at every intermediate vertex
Maximize flow sent from s to t
Flow
Flow: function f: V × V → R≥0 satisfying:
Capacity: f(u,v) ≤ c(u,v) for all u, v ∈ V
Conservation: for all v∈ V – {s, t},
i.e., flow entering v = flow leaving v
Flow
Value of flow |f|:
i.e., value of flow is sum of flow out of the source
Maximum Flow Problem
Given a network G = (V, E, s, t, c), find a flow f of maximum value.
Flows and Cuts
Flow across cut:
Capacity of cut:
Fact 1: f(S) ≤ c(S) by capacity constraint
Flows and Cuts
Fact 2: All s-t cuts have the same flow
Theorem: f(S) = |f| for all s-t cuts (S, V – S)
Proof: by induction on |S|
Basis: S = {s} → f(S) = |f| by definition of |f|
Inductive step: ∃x ≠ s with x ∈ S
f(S) = f(S – {x}) – f(S – {x},x) + f(x, V – S)
= |f| + f(x, S – {x}) + f(x, V – S) (by IH & conservation)
= |f| (by conservation)
☐
Max Flow and Min Cut
Max flow ≤ min cut
Proof: for any flow f and cut (S, V – S):
|f| = f(S) (by fact 2)
f(S) ≤ c(S) (by fact 1)
thus |f| = f(S) ≤ c(S) ☐
Max-Flow Min-Cut Theorem
Max-flow min-cut theorem. In any network, the value of the max flow equals the capacity of the min cut:
|max flow| = c(min cut)
Proof: Later.
Idea for an Algorithm
Find a path in G from s to t where each edge on path has f(u,v) < c(u,v) and “augment”, i.e., increase, flow along it
Repeat until there are no more augmenting paths
Residual Network
Residual network Gf = (V, Ef) of flow f in network G:
capacities cf(u,v) = c(u,v) – f(u,v)
(how much extra flow edge (u,v) can handle)
edges (u,v) ∈ Ef whenever cf(u,v) > 0
(discard saturated edges)
If f’ is a flow in Gf then f + f’ is a flow in G
max flow in G = f + max flow in Gf , for all f
Augmenting Paths
Augmenting path: directed s → t path p in Gf
Can push additional flow along such path p, up to cf(p) = min{cf(u,v) : (u,v) edge of p}
If there is an augmenting path in Gf, then f is not a max flow
In fact: if there are no augmenting paths in Gf, then f is a max flow
Ford-Fulkerson Augmenting Path Algorithm
Ford-Fulkerson(G = (V, E, s, t, c))
01 f(u,v) = 0 for each edge (u,v) in E
02 while (there exists an augmenting path)
03 find an augmenting path p
04 compute residual capacity cf(p) of p
05 augment flow f along p
06 return f
Ford-Fulkerson Augmenting Path Algorithm
Questions:
Does this algorithm lead to a max flow in G?
How find an augmenting path in Gf(V, Ef)?
How many augmenting paths until convergence?
How much time to find each augmenting path?
Proof of Max-Flow Min-Cut Theorem
Theorem: Value of max flow = capacity of min cut.
Proof: Suppose f is max flow with no augmenting paths.
Then residual graph Gf has no s → t paths.
Let S = {vertices reachable from s in Gf}.
(S, V – S) is an s-t cut (since s∈S and t ∉ S).
for all u∈ S, v ∈ V – S: cf(u,v) = 0 (no residual edges)
Thus c(u,v) = f(u,v) (since cf(u,v) = c(u,v) – f(u,v))
Thus c(S) = f(S) = |f|
But |max flow f| ≤ c(min cut S)
So f is max flow & S is min cut & equal. ☐
Ford-Fulkerson Algorithm: Analysis
Analysis: O(E) time per augmentation
If capacities are integers ∈[0, C], then at most
|f| ≤ |V|· C augmentations, where C is max capacity
If C = 1, then algorithm runs in ≤ |V| iterations
Time: O(EV · C), “pseudopolynomial”
C can be very large: inefficiencies due to C
Choosing Good Augmenting Paths
This can happen: Paths 1 & 2 alternate:
2 · 106 iterations possible
Edmonds-Karp Shortest Path Algorithm
Shortest augmenting path algorithm
Version of Ford-Fulkerson: uses BFS to find augmenting paths with fewest number of edges
Analysis: at most O(VE) augmentations
O(VE2) total running time
Edmonds-Karp Algorithm Notes
Pseudocode that follows uses incident matrix format for input graph G.
Residual graph is defined on line 2 as Gr. Gr[i][j] denotes capacity of edge from i to j. Gr[i][j] = 0 if no edge from i to j.
Lines 3-5 set residual capacity of each edge in residual graph to the capacity of each edge in original graph, G.
Edmonds-Karp Algorithm Notes
Algorithm continues as long as a path has been found by BFS at line 8.
Lines 10-12 find minimum flow on the shortest path that remains in residual graph Gr.
Lines 13-18 update the residual capacities of the edges along this path in Gr and add flow along this path to the overall flow.
Edmonds-Karp Max-Capacity Algorithm
“Fattest” augmenting path algorithm
Version of Ford-Fulkerson: uses Dijkstra to find augmenting path with maximum capacity
Analysis:
O(E log V) per augmentation with binary heap
O(E log C) augmentations where C is max capacity
O(E2 log V log C) total running time
Max-flow improvements
Research improvements:
Push-relabel algorithms: O(V2E)
Dynamic trees: O(EV log V)
Flow blocking: O(E3/2 log (V2/E) log C)
Practice:
max flow on unbalanced bipartite graphs
Image segmentation
Maximum Bipartite Matching
Input: undirected bipartite graph G = (L∪R, E)
Set of edges M ⊆ E is a matching if each vertex v ∈ V appears at most once in M
Maximum matching problem: find a max cardinality matching in G
Matching M: {(Al, Beatrice), (Bob, Danielle), (Chet, Alice), (Dan, Carol)}
R
L
Finding a Max Bipartite Matching
Reduce to max flow:
Create a directed graph G’:
Create source vertex s, with outgoing edges from s to each vertex in L
Create sink vertex t, with incoming edges from each vertex in R to t
Direct all edges in original bipartite graph G from L to R
Give all edges in G’ capacity 1
Run Ford-Fulkerson on G’ to find max flow
Flow Network: Each edge has capacity of 1
L
R
Bipartite Matching: Correctness
Claim. Matching in G of cardinality k induces flow in G’ of value k.
Proof: Given matching M = {(Al, Beatrice), (Bob, Danielle), (Chet, Alice), (Dan, Carol)} of cardinality 4.
Consider flow f that sends 1 unit along each of 4 paths: s-Al-Beatrice-t, s-Bob-Danielle-t, s-Chet-Alice-t, s-Dan-Carol-t.
f is a flow, and has cardinality 4. ☐
Bipartite Matching: Correctness
Claim. Flow f of value k in G’ induces matching of cardinality k in G.
Proof: Since G’ has integer capacities, max flow f found by Ford-Fulkerson is integral, |f|= k.
Let M = set of edges from L to R with f(u,v) = 1.
Each vertex in L and R is incident to at most one edge in M.
Thus |M|= k = 4. ☐
Reduction
Given an instance of bipartite matching.
Reduce it to a max flow problem.
Solve max flow problem. (Use Ford-Fulkerson)
Transform max flow solution to bipartite matching solution.
Analysis
Cost of creating flow network: O(V + E)
Cost of Ford-Fulkerson: O(|M|· E) = O(VE),
since |M| = O(V)
Total cost: O(V + E) + O(VE) = O(VE)
/docProps/thumbnail.jpeg