1 of 39

Lecture 19

Max Flow III

CSE 421 Autumn 2025

1

2 of 39

Previously…

2

3 of 39

The maximum flow problem

Input: a flow network

Output: a s-t flow of maximum value

3

i.e. what’s maximum rate at which water can flow from from to ?

4 of 39

The minimum cut problem

Input: a flow network

Output: a s-t cut of minimum capacity

4

5 of 39

Cuts limit flows (“Weak duality”)

5

Lemma: Let be any - flow, and let be any - cut. Then,

.

Goal: show that cuts are the only thing that limit flows, i.e. that the there is a flow that achieves the minimum capacity cut�(this would prove the Max Flow-Min Cut theorem)

Our strategy to prove this: let’s think about how to find the max flow (and hope to discover useful structural properties)!

6 of 39

Augmenting paths through residual flow

6

7 of 39

Augmenting paths through residual flow

7

8 of 39

Augmenting paths through residual flow

8

9 of 39

Augmenting paths through residual flow

9

Note: since the middle edges in the two graphs are in opposite directions, we subtract one from the other!

10 of 39

Residual network definition

For and flow , define as the residual network with the same vertices, source and sink , and: for every edge ,

  • (Forward edge): Add an edge of capacity , if .
  • (Backward edge): Add an edge of capacity , �if .

10

11 of 39

Ford-Fulkerson algorithm

  • Initialize a flow for all edges. Set residual network
  • While there is a simple path in
    • Let be the flow along path where each edge has flow
    • For every edge , let be the corresponding original edge in : update �(i.e. count forward edges as +, and backward edges as -)
    • Compute the new residual graph (only need to update edges along ).

Call this the bottleneck capacity of the path

12 of 39

Ford-Fulkerson algorithm

12

Lemma: The value of increases at every iteration.

Proof: At each iteration, we perform the update:

Could decrease the flow on some edges

Since the value of a flow is, by definition, , we have shown that the value of increases.

Notice that, in the augmenting path , the edge containing must be a forward edge (so it contributes positively to , the flow out of ).

Why?

Because, in the original graph, only has outgoing edges, so backward edges of any residual graph must be of the form , and so they are not on a path .

13 of 39

Ford-Fulkerson algorithm

  • Initialize a flow for all edges. Set residual network .
  • While there is a simple path in
    • Let be the flow along path where each edge has flow
    • For every edge , let be the corresponding original edge in : update �(i.e. count forward edges as +, and backward edges as -)
    • Compute the new residual graph (only need to update edges along ).

Runtime

Run any graph traversal to find such a path: time

time

How many iterations in the while loop?

14 of 39

Ford-Fulkerson algorithm

Runtime

How many iterations in the while loop?

So, there are at most iterations, where is the Max Flow.

Suppose the capacities are integers, then each iteration increases the value at least by 1.

So, overall, runtime is . Can simplify this to since we can ignore “isolated” vertices, and there are at most vertices that are not isolated.

15 of 39

Today

15

  • Proving correctness of Ford-Fulkerson
  • Proving the Max Flow-Min Cut theorem
  • Applications of Max Flow

16 of 39

Ford-Fulkerson animation

16

17 of 39

Ford-Fulkerson animation

17

18 of 39

Ford-Fulkerson animation

18

19 of 39

Ford-Fulkerson animation

19

20 of 39

Ford-Fulkerson animation

20

21 of 39

Ford-Fulkerson animation

21

22 of 39

Ford-Fulkerson animation

22

23 of 39

Ford-Fulkerson animation

23

24 of 39

Ford-Fulkerson animation

24

25 of 39

Ford-Fulkerson animation

25

26 of 39

Ford-Fulkerson animation

26

27 of 39

Ford-Fulkerson animation

27

28 of 39

Ford-Fulkerson animation

28

29 of 39

Ford-Fulkerson animation

29

“Weak duality”: the value of a flow can never exceed any cut’s capacity.

30 of 39

Ford-Fulkerson always finds a max flow

30

Have we already proven that Ford-Fulkerson finds the Max Flow?

No.

We have only shown that the flow always increases as long as we are still in the while loop.

Since the Max Flow is finite, this shows that the algorithm terminates.

But it could in principle terminate before it finds the Max Flow.

31 of 39

Ford-Fulkerson always finds a max flow

Theorem: When capacities are positive integers, Ford-Fulkerson outputs a max-flow.

Observation: Ford-Fulkerson only terminates if there is no path in the residual graph .

Therefore, it suffices to show that a flow is maximal when there is no path in the residual graph .

31

32 of 39

Ford-Fulkerson always finds a max flow

32

We will prove that:

No path in .

There exists a s-t cut such that .

This implies would imply is maximal.

Why?

By weak duality, for all . So, if , then is maximal.

33 of 39

Ford-Fulkerson always finds a max flow

Proof:

  • Let be a flow such that there are no augmenting paths in .
  • Let be the set of vertices reachable from in .
  • Since there are no paths , then .
  • Let . Then is an s-t cut.

33

No path in .

There exists a s-t cut such that .

34 of 39

Ford-Fulkerson always finds a max flow

Proof:

  • What does it mean for there to be no edges to in the residual graph ?
  • For any edge from to ,

34

No path in .

There exists a s-t cut such that .

35 of 39

Ford-Fulkerson always finds a max flow

Proof:

  • What does it mean for there to be no edges to in the residual graph ?
  • For any edge from to ,

35

No path in .

There exists a s-t cut such that .

36 of 39

Ford-Fulkerson always finds a max flow

Proof:

  • What does it mean for there to be no edges to in the residual graph ?
  • For any edge from to ,

36

No path in .

There exists a s-t cut such that .

37 of 39

Ford-Fulkerson always finds a max flow

Proof:

  • Edges from to are saturated with flow.
  • Edges from to have no flow.

37

No path in .

There exists a s-t cut such that .

So is maximal! (by Weak Duality, as argued earlier)

Recall:

38 of 39

Back to the max flow-min cut theorem..

38

Theorem: The value of the maximum flow from to is equal to the value of the minimum capacity - cut (i.e. minimum capacity cut separating and ).

Have we proved it?

What we had earlier:

Step 1. (“weak duality”) The capacity of any - cut is an upper bound on the maximum flow (in particular, the minimum - cut is an upper bound on the maximum flow).

Our proof of correctness of Ford-Fulkerson says something powerful: �not only Ford-Fulkerson finds the Max-Flow, but the output of Ford-Fulkerson achieves the capacity of some cut! (in fact, of the minimum capacity cut, by weak duality).

So we are done!

Another instance of proving a theorem by considering an algorithm!

39 of 39

Ford-Fulkerson: summary

  • Ford-Fulkerson is a (sophisticated!) greedy algorithm that calculates the max flow by incrementally increasing the flow.
  • When it terminates, the max flow is achieved.
  • If the capacities are integer, Ford-Fulkerson will increase the flow by at least 1 per iteration.
  • Yields a runtime of where is the sum of capacities of edges leaving .
  • Runtime can be exponential time in input length for large as capacities are take only bits to express in binary.
  • But when , then algorithm can be very efficient.

39