CSC373H Lecture 7
CSC373H Lecture 7
Dan Zingaro
October 27, 2021
Residual Networks
▶ Sometimes it is necessary to decrease flow along one or more
edges to increase flow overall
▶ We can formalize this idea by using a residual network Gf and
finding augmenting paths in there instead of in G
▶ We use the following rules (don’t include edges with 0
capacity)
cf (u, v) =
c(u, v)− f (u, v), if (u, v) ∈ E
f (v , u), if (v , u) ∈ E
0, otherwise
Residual Network: Example (Overview)
Residual Network: Example (Flow Network)…
Residual Network: Example (Residual Network)…
Augmenting Paths, Take 2
▶ Now let’s find an augmenting path in Gf and use it to
augment flow in G
▶ Define the residual capacity of an augmenting path p in the
residual network to be cf (p) = min{cf (u, v) : (u, v) is on p}
▶ We add cf (p) to the flow of each forward edge in G and
subtract cf (p) from the flow of each backward edge in G
▶ This is the correct Ford-Fulkerson method
Ford-Fulkerson Method
ford-fulkerson(G, s, t):
for each edge (u, v) in E:
f(u, v) <- 0 while there exists a path p from s to t in Gf: cf(p) <- min {cf(u, v) : (u, v) on p} for each edge (u, v) on p: if (u, v) is an edge in G: f(u, v) <- f(u, v) + cf(p) else: # (v, u) is an edge in G f(v, u) <- f(v, u) - cf(p) Augmenting Along a Path Increases Flow Augmenting the flow along a path in Gf ▶ maintains the capacity constraints ▶ maintains the conservation constraint, and ▶ increases the flow value ▶ You can formally prove these if you like! Correctness of Ford-Fulkerson ▶ Ford-Fulkerson is correct iff we can prove two things ▶ (1) If f is a maximum flow in G then Gf has no augmenting paths ▶ (2) If Gf has no augmenting paths then f is a maximum flow in G ▶ We can do part (1) of the proof now ▶ Contradiction proof: suppose f is a maximum flow but there is an augmenting path in Gf ▶ Then we can use that augmenting path to get a better flow than the supposed maximum flow f ▶ But proving part (2) isn’t so easy ▶ It’s easier if we take a scenic route to prove it using cuts . . . Cuts ▶ A cut (S ,T ) of a flow network G = (V ,E ) is a partition of V such that ▶ s ∈ S ▶ t ∈ T ▶ S and T are disjoint and V = S ∪ T Cuts... We can define the flow and the capacity of a cut. ▶ Flow f across cut (S ,T ) is the flow from S to T minus the flow from T to S ▶ ∑ u∈S ∑ v∈T f (u, v)− ∑ u∈S ∑ v∈T f (v , u) ▶ Capacity c of cut (S ,T ) is the capacity from S to T (has nothing to do with the capacity from T to S!) ▶ ∑ u∈S ∑ v∈T c(u, v) Cuts: Example Consider cut ({s, v1, v2}, {v3, v4, t}). What is the flow across this cut? What is the capacity of the cut? Cuts: Flow and Capacity ▶ On the previous slide, we saw that the flow across the cut equaled |f | ▶ And we saw that |f | was less or equal to the capacity of the cut ▶ These are not coincidences ▶ We can prove that |f | = f (S ,T ) for any cut (S ,T ) and flow f ▶ Annoying proof — study details in textbook ▶ We can also prove that |f | ≤ c(S ,T ) for any cut (S ,T ) and flow f . We’ll do this now! Flow Values are Less than Cut Capacities We show that for any flow f and cut (S ,T ), we have |f | ≤ c(S ,T ). |f | = f (S ,T ) (previous slide) = ∑ u∈S ∑ v∈T f (u, v)− ∑ u∈S ∑ v∈T f (v , u) (flow across cut) ≤ ∑ u∈S ∑ v∈T f (u, v) (capacity constraint) ≤ ∑ u∈S ∑ v∈T c(u, v) (capacity constraint) = c(S ,T ) (capacity of cut) Consequence: value of a maximum flow is ≤ minimum capacity of any cut. Proving Part (2) ▶ Remember that our goal here is to prove that a flow is maximum iff the residual network contains no augmenting paths ▶ Earlier, we proved one half: that if a flow is maximum then the residual network has no augmenting paths ▶ We prove the other half in two steps ▶ (A) Prove that if the residual network has no augmenting paths then |f | = c(S ,T ) for some cut (S ,T ) ▶ (B) Prove that if |f | = c(S ,T ) for some cut (S ,T ), then f is a maximum flow Proving Part (2)... (A) Prove that if the residual network has no augmenting paths then |f | = c(S ,T ) for some cut (S ,T ). ▶ We assume that Gf has no augmenting paths (i.e. no path from s to t) ▶ Let S be the vertices reachable from s in Gf and T = V − S ▶ (S ,T ) is a cut: s ∈ S and t ̸∈ S because t is not reachable from s ▶ Consider u in S and v in T . (u, v) is not in Gf , otherwise v would be reachable from s ▶ If (u, v) ∈ E , then c(u, v)− f (u, v) must be 0 to keep (u, v) out of Gf ▶ So in this case, f (u, v) = c(u, v) ▶ If (v , u) ∈ E , then f (v , u) must be 0 to keep (u, v) out of Gf |f | = f (S ,T ) = ∑ u∈S ∑ v∈T f (u, v)− ∑ v∈T ∑ u∈S f (v , u) = ∑ u∈S ∑ v∈T c(u, v) = c(S ,T ) Proving Part (2)... (B) Prove that if |f | = c(S ,T ) for some cut (S ,T ), then f is a maximum flow. ▶ We have already established that |f | ≤ c(S ,T ) for any cut (S ,T ) ▶ That is, |f | is at most c(S ,T ) ▶ And we are given here that |f | is exactly that maximum value c(S ,T ) ▶ f is therefore a maximum flow Choosing Bad Paths Ford-Fulkerson can be terribly inefficient. Watch what happens if we choose the wrong augmenting paths in this flow network! Runtime of Ford-Fulkerson ▶ If we choose arbitrary augmenting paths: O(mf ∗), where f ∗ is the value of a maximum flow ▶ Why? Because we really might end up doing f ∗ iterations ▶ This is not a polynomial-time algorithm! ▶ We have to be able to do better than this! Capacity Scaling ▶ Capacity scaling is based on the Ford-Fulkerson method ▶ Idea: first use all augmenting paths where each edge has at least a high capacity δ (this way we can’t use a path with residual capacity 1 when way better paths are still available) ▶ Then repeat with δ/2, δ/4, etc. until all edges are allowed back in ▶ Using this idea, we get O(lg f ∗m2) runtime — counts as polynomial time Edmonds-Karp ▶ Edmonds-Karp is also based on the Ford-Fulkerson method ▶ Idea: use BFS to choose augmenting paths of fewest edges ▶ This also avoids the terrible runtime we saw in the last example ▶ Key reason: augmentations are guaranteed to quickly make s and t further and further apart until they are disconnected ▶ Using this idea, we get O(nm2) runtime — strongly polynomial-time now! Other Algorithms ▶ There are all kinds of other techniques for finding max flow ▶ e.g. Push-Relabel algorithms ▶ Unlike Ford-Fulkerson, these algorithms disconnect s and t from the start ▶ But to do that, they use invalid flows that they slowly repair into valid flows ▶ But we won’t study them here, because what we have so far is fast enough ▶ We can now use our max-flow algorithms to solve other problems ▶ The max-flow algorithm doesn’t change; only the problem that we are solving changes Max-Flow Min-Cut Theorem We have shown that these three are equivalent: ▶ (i) f is a maximum flow in G ▶ (ii) Gf has no augmenting paths ▶ (iii) |f | = c(S ,T ) for some cut (S ,T ) Since (i) and (iii) are equivalent, we get the uber-famous Max-Flow Min-Cut Theorem: In every flow network, the maximum value of a flow equals the minimum capacity of a cut. Who Cares About Min Cut? ▶ Max flow: make best use of flow network ▶ Min cut: minimum damage required to completely disconnect flow network ▶ Min cut is itself a very useful problem to be able to solve ▶ And we already have a solution: just find the cut that we used when we proved 2 (A)!