Lecture 18

Max Flow II

CSE 421 Autumn 2025

1

Previously…

2

Flow network definition

• Imagine each edge in a graph is a directional water pipe
• Each edge has a capacity for
• There are two specified vertices for source (only outgoing edge) and sink (only incoming edges)
• graph
• A flow network is a tuple

3

s-t flow

• A s-t flow in a flow network is a function that satisfies:
• For each edge ,
• For every ,��.
• The value of a flow is

4

= net flow into (due to conservation)!

The maximum flow problem

• Input: a flow network
• Output: a s-t flow of maximum value

5

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

Graph cuts

• An s-t cut in a graph is a partition of the vertices into such that and . The capacity of a s-t cut is

6

Graph cuts

• An s-t cut in a graph is a partition of the vertices into such that and . The capacity of a s-t cut is

7

Graph cuts

• An s-t cut in a graph is a partition of the vertices into such that and . The capacity of a s-t cut is

8

The minimum cut problem

• Input: a flow network
• Output: a s-t cut of minimum capacity

9

Cuts limit flows (“Weak duality”)

10

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)!

Finding the Max Flow

11

First idea: find a path that we can push flow along.

More precisely:

• Start with the trivial (zero) flow.
• Find a path such that each edge has some remaining capacity.
• Add flow to this path.

Finding the Max Flow

12

First idea: find a path that we can push flow along.

More precisely:

• Start with the trivial (zero) flow.
• Find a path such that each edge has some remaining capacity.
• Add flow to this path. How much can you add?

Finding the Max Flow

13

First idea: find a path that we can push flow along.

More precisely:

• Start with the trivial (zero) flow.
• Find a path such that each edge has some remaining capacity.
• Add flow to this path. How much can you add? You can add the minimum remaining capacity of any edge in the path.
• Greedy: repeat this as much as you can.

Finding the Max Flow

14

First idea: find a path that we can push flow along.

More precisely:

• Start with the trivial (zero) flow.
• Find a path such that each edge has some remaining capacity.
• Add flow to this path. How much can you add? You can add the minimum remaining capacity of any edge in the path.
• Greedy: repeat this as much as you can. Does this work?

Finding the Max Flow

15

First idea: find a path that we can push flow along.

You’ll find a valid flow: each augmentation respects capacity constraints and conservation of flow.

More precisely:

• Start with the trivial (zero) flow.
• Find a path such that each edge has some remaining capacity.
• Add flow to this path. How much can you add? You can add the minimum remaining capacity of any edge in the path.
• Greedy: repeat this as much as you can. Does this work?

But it may not be optimal.

Finding the Max Flow

16

First idea: find a path that we can push flow along.

More precisely:

• Start with the trivial (zero) flow.
• Find a path such that each edge has some remaining capacity.
• Add flow to this path. How much can you add? You can add the minimum remaining capacity of any edge in the path.
• Greedy: repeat this as much as you can. Does this work?

optimal

Today

17

• Ford-Fulkerson algorithm for Max Flow

Naive greedy algorithm is suboptimal

• What if there was a way to “undo” a choice made by a greedy algorithm and keep going?
• Key idea: Consider "residual graphs”.
• A graph that represents how much we can change for any edge
• If an edge has a capacity and the current flow assigns it :
• We can either add up to additional flow
• Or remove up to flow from this edge.

18

Augmenting paths through residual flow

19

Augmenting paths through residual flow

20

Augmenting paths through residual flow

21

Augmenting paths through residual flow

22

Why is overall flow larger?

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 .

23

Notation

• For a flow , let
• Conservation of flow: .
• Capacity constraint: .

24

New greedy algorithm (Ford-Fulkerson)

• 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 ).

Q1: Is it clear that, at every iteration, is still a valid flow?

Q2: Is it clear that, at every iteration, the value of increases?

New greedy algorithm (Ford-Fulkerson)

26

Q1: Is it clear that, at every iteration, is still a valid flow?

Lemma: remains a valid flow at every iteration.

Proof: At each iteration, we perform the update:

Recall that is a flow along a path , with a constant value of on each edge of , where was the bottleneck capacity of .

The net flow through each vertex is unchanged!

(so conservation is still satisfied)

Moreover,

So, the capacity constraint is also satisfied

New greedy algorithm (Ford-Fulkerson)

27

Q2: Is it clear that, at every iteration, the value of increases?

Lemma: The value of increases at every iteration.

Proof: At each iteration, we perform the update:

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 .

New greedy algorithm (Ford-Fulkerson)

• 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

One option is to run graph traversal: time

How many iterations in the while loop?

New greedy algorithm (Ford-Fulkerson)

Runtime

How many iterations in the while loop?

Suppose the capacities are integers

New greedy algorithm (Ford-Fulkerson)

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.

It’s a bit strange that the runtime is in terms of the answer, but such is life sometimes..

So, overall, runtime is

New greedy algorithm (Ford-Fulkerson)

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.

It’s a bit strange that the runtime is in terms of the answer, but such is life sometimes..

So, overall, runtime is .

New greedy algorithm (Ford-Fulkerson)

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.

It’s a bit strange that the runtime is in terms of the answer, but such is life sometimes..

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