Lecture 20

Max Flow IV

CSE 421 Autumn 2025

1

Previously…

2

The maximum flow problem

Input: a flow network

Output: a s-t flow of maximum value

3

The minimum cut problem

Input: a flow network

Output: a s-t cut of minimum capacity

4

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.

5

The Max Flow-Min Cut theorem

6

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

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

Step 2. 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).

Another instance of proving a theorem by considering an algorithm!

Proved in two steps:

Today

7

• Applications of Max Flow
• Faster Max Flow algorithms

Integer capacities imply integer max flow

Theorem: Consider a graph network where . Then, there exists a max flow which assigns an integer flow to every edge.

Proof:

• Ford-Fulkerson starts with the trivial (zero) flow.
• Ford-Fulkerson only increases the flow by integer quantities starting from 0 (since it considers the “bottleneck capacity” at each step, which is an integer)
• Therefore, there exists a max flow where the flow on every edge is integer.

8

This should be very believable by now. But let’s be clear:

Applications

9

Max Flow and Min Cut are useful if you work for a water company..

But they are also useful if you don’t.

The most common application is assignment/matching problems.

Big idea: let one unit of flow mean “assigning” one job to a person.

Application: Bipartite matching

Input: A bipartite graph

Output: A maximal collection of edges that don’t share any vertices.

10

Application: Bipartite matching

Input: A bipartite graph

Output: A maximal collection of edges that don’t share any vertices.

11

Imagine: jobs on the left, and applicants on the right.�Edges represent pairs that are OK with each other.

Think about: how does this differ from stable matching?

The goal is to match as many pairs as possible.

Application: Bipartite matching

Input: A bipartite graph

Output: A maximal collection of edges that don’t share any vertices.

​

To cast this as a Max-Flow problem, we need to create a directed graph and identify a source and sink .

12

Application: Bipartite matching

13

Application: Bipartite matching

14

Application: Bipartite matching

15

Application: Bipartite matching

16

Application: Bipartite matching

Claim: The middle edges of flow 1 in the max flow form a maximal bipartite matching.

Proof:

There is a bijection between matchings and integer flows:�matching of size integer flow of value

Why?

17

Application: Bipartite matching

Claim: The middle edges of flow 1 in the max flow form a maximal bipartite matching.

Proof:

There is a bijection between matchings and integer flows:�matching of size integer flow of value

Why? Fix an integer flow. By construction, all edges have capacity 1, and each has only one incoming edge. So each can have at most one outgoing edge of flow 1. �Likewise, since each has only one outgoing edge, each can have at most one incoming edge of flow 1.

18

the vertices in and involved in an edge of flow 1 are paired 1-to-1, i.e.�they form a valid matching. If the matching is of size , the flow is of size as it includes the edges from the source and to the sink.

Application: Bipartite matching

Claim: The middle edges of flow 1 in the max flow form a maximal bipartite matching.

Proof:

There is a bijection between matchings and integer flows:�matching of size integer flow of value

For the inverse map, given any matching of size :

• Assign flow 1 to each edge connecting a matching pair.
• Assign flow 1 to any edge connecting the source to a “left” vertex in the matching.
• Assign flow 1 to any edge connecting a “right” vertex in the matching to the sink.

19

This bijection implies that the Max Flow corresponds to the maximal bipartite matching.

Application: Bipartite matching

Runtime:

• Each edge has capacity , and the source has total outgoing capacity (if is the number of vertices in the bipartite graph).
• Number of edges in the network is .
• Total runtime after reduction, .

20

Ford-Fulkerson can be slow

Input: The input is a flow network (with integer capacities)

• Formally, where is a number (of bits, where is the maximum capacity).
• Runtime of Ford-Fulkerson is .
• Note: is exponential in , so the runtime is exponential in the input-length!
• The factor of is due to the fact that the flow may only increase by 1 at each iteration.
• Is there a way to find larger increases in flow at each iteration?

21

Ford-Fulkerson can be slow

• We previously chose an arbitrary augmenting path in .
• This may fail to find an augmenting path of large bottleneck capacity (recall that the bottleneck capacity is the amount by which the flow value increases)
• Can we modify the algorithm so that we select a pretty large augmenting path?

22

Finding a pretty large augmenting path

“Capacity-scaling” Ford-Fulkerson:

Let . Set .

We maintain a scaling parameter . Initialize .

While :

• Consider the -residual graph, i.e. only edges with capacity .
• While there is an path in this residual graph, find any such path and augment along it (this increases the flow by at least ). Update the residual graph.
• When no such path exists, update and repeat.

23

The idea: In the early phase, we only consider “highways” with high capacity. As lowers, we start considering the smaller “roads”, and we never go back to the larger scales.

Finding a pretty large augmenting path

“Capacity-scaling” Ford-Fulkerson:

Let . Set .

We maintain a scaling parameter . Initialize .

While :

• Consider the -residual graph, i.e. only edges with capacity .
• While there is an path in this residual graph, find any such path and augment along it (this increases the flow by at least ). Update the residual graph.
• When no such path exists, update and repeat.

24

Runtime:

Finding a pretty large augmenting path

“Capacity-scaling” Ford-Fulkerson:

Let . Set .

We maintain a scaling parameter . Initialize .

While :

• Consider the -residual graph, i.e. only edges with capacity .
• While there is an path in this residual graph, find any such path and augment along it (this increases the flow by at least ). Update the residual graph.
• When no such path exists, update and repeat.

25

Runtime: There are possible values for the scaling parameter .

• How many iterations per ? One can show that there are at most augmenting paths per . So iterations total.
• How much time per iteration? One graph traversal and updates: .
• Total runtime:

Other Max Flow algorithms

So far, for integer capacities:

Original Ford-Fulkerson: runtime

• Pick any augmenting path

“Capacity-scaling” Ford-Fulkerson: runtime

• Find large augmenting paths first and gradually lower the scale

26

Are there algorithms where runtime is independent of ?

Edmonds-Karp algorithm

27

Edmonds-Karp’s idea: pick the shortest augmenting path (in terms of # of edges)

Ford-Fulkerson gives a template: pick a path in the residual graph.

Recall..

Follows the Ford-Fulkerson template, but with a particular instantiation for how to pick augmenting paths.

Edmonds-Karp algorithm

• Initialize and
• While there is a path in :
• Pick the shortest path (# of edges)
• Compute bottleneck capacity and update by augmenting along at capacity . Update .
• Output resulting flow .

28

Recall: BFS finds the shortest path! (vertices are discovered in order of distance from the source)

Edmonds-Karp algorithm

• Initialize and
• While there is a path in :
• Run BFS to find shortest path (# of edges)
• Compute bottleneck capacity and update by augmenting along at capacity . Update .
• Output resulting flow .

29

Claim: Only iterations are needed to find the max flow!

Edmonds-Karp algorithm

• Every time an augmenting path is chosen, the bottleneck edge becomes saturated — i.e. . As a result, distances from the source never decrease in the residual graph (backward edges also don’t help).
• It suffices to show that each edge can only be the bottleneck in at most augmenting paths. Since there are edges, this would yield a max of iterations.
• Key idea: show that each time an edge is involved in a shortest path, the distance from to one of its endpoints (in the residual graph) has increased by at least 2.

30

Claim: Only iterations are needed to find the max flow!

Proof ideas:

Max Flow algorithms

For integer capacities:

Original Ford-Fulkerson: runtime

• Pick any augmenting path

“Capacity-scaling” Ford-Fulkerson: runtime

• Look for augmenting paths with high bottleneck capacity first

Chen, Li, Liu, Peng, Probst Gutenberg, Sachdeva [2022!]: runtime

31

For non-integer capacities:

Edmondson-Karp: runtime

• Pick the shortest augmenting path (in terms of # of edges)