Algorithms and Data Structures 2

Maximum Flow

Kathrin Hanauer Gramoz Goranci

Theory and Application of Algorithms (TAA)

Faculty of Computer Science

Winter Semester 2023

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 1
Acknowledgements
Material based on slides by Monika Henzinger, Christian Schulz
Original slides by Kurt Mehlhorn, Peter Sanders, and Rob van Stee

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 2
Definitions: Flow Network
▶ Flow Network: directed, weighted, simple graph G = (V , E , c, s, t) with
distinguished source node s and sink node t
simple graph: no pairs of anti-parallel edges, no loops
▶ We use n := |V | and m := |E |
▶ Weight c(e) of an edge e is called the capacity of e , c(e) ≥ 0
▶ Generalization of c to V × V : c(u, v ) = 0 if (u, v ) ̸∈ E

10
u v
12
10

4
s 4 t

10 8
w x
4
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 3
Definitions: Flow
A flow is a function f : V × V → R that satisfies
▶ ∀(u, v ) ∈ V × V : 0 ≤ f (u, v ) ≤ c(u, v ) (capacity constraints)
▶ ∀v ∈ V \ {s, t} :
P P
f (u, v ) = f (v , u) (flow conservation)
u∈V u∈V
The value |f | of a flow f is the flow leaving s minus the flow entering it:
P P
|f | = f (s, v ) − f (v , s) ≥ 0.
v ∈V v ∈V

Maximum flow: a flow of maximum value

8/10
u v
0 12
/1 /1
10 2

2/
4
s 4/
4 t

8/ 8
10 6/
w x |f | = 10 + 8 = 18
4/4

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 4
Definitions: s-t Cut
▶ s -t cut: partition (S, T ) of V such that s ∈ S and t ∈ T
▶ Let E (S, T ) = {(u, v ) ∈ E | u ∈ S ∧ v ∈ T } = E ∩ (S × T )
▶ The capacity of a cut is c(S, T ) =
P P
c(u, v ) = c(e)
u∈S,v ∈T e∈E (S,T )
Minimum s -t cut: a cut of minimum capacity

10
u v
12
10

4
s t
S
4
10 8
w x T
4

c({s, w } , {u, v , x , t}) = 10 + 4 + 4 = 18

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 5
Applications

▶ Oil pipes
▶ Traffic flows on highways
▶ Computer Vision
• Image Smoothing
• Image Segmentation
• Stereo Processing
• Multiview Reconstruction
• Panoramas
• ...
▶ Bipartite Matching
▶ Network Reliability
▶ Scheduling
▶ Matrix Rounding
▶ ...

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 6
A (Too) Greedy Algorithm
0 Set f (e) = 0 ∀e ∈ E .

1 Try to find a path P = s ; t such that each edge e has

P P spare capacity, i. e. , f (e) < c(e).

3 Terminate. 2 Augment the flow along P by the minimum spare ca-

pacity.

8 10/10
u v
2 12
10 /1
0/ 2

0/
1

4
s t
4
4
2/

6/ 8
1 4/
8 0 18
w x 6
4/4 |f | = 16

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 7
Residual Graph

Given a network G = (V , E , c, s, t) and a flow f , the residual network is a graph

Gf = (V , Ef , cf , s, t), where reverse edge (v , u) of e = (u, v )
▶ Ef = {e | e ∈ E ∧ f (e) < c(e)} ∪ {e rev | e ∈ E ∧ f (e) > 0},
(
c(e) − f (e), if e ∈ E (remaining capacity)
▶ cf (e) = (residual capacity)
rev rev
f (e ), if e ∈ E (cancellable flow)

10/10
u v u v
12 10
10 /1 4
0/ 2
0/

1
12
4

10
s t s t
4 4

2
4
2/

6/ 8 2
10 4/ 6 4
w x w x
4/4 4

flow network G with flow f corresponding residual graph Gf

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 8
Augmenting Paths

An augmenting path is a simple path P = s ; t in Gf .

The residual capacity or bottleneck capacity of an augmenting path P is

cf (P) = min cf (e).
e on P
A bottleneck edge is an edge on P ( with cf (e) = cf (P).
cf (P), if (u, v ) is on P,
Let fP : V × V → R with fP (u, v ) =
0, otherwise.
Then, fP is a flow in Gf and |fP | = cf (P) > 0.

u v
10
4
12
10
s t
4 4
2

6 2
4
w x
4

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 9
Augmenting Paths

Lemma
If f is a flow in a network G = (V , E , c, s, t) and P is an augmenting path in Gf , then
f + fP : V × V → R with (
f (u, v ) + fP (u, v ) − fP (v , u), if (u, v ) ∈ E
(f + fP )(u, v ) =
0, else.
is a flow in G with |f + fP | = |f | + |fP |.

Proof.
Capacity constraints: ∀(u, v ) ∈ V × V : 0 ≤ (f + fP )(u, v ) ≤ c(u, v ).
If (u, v ) ̸∈ E , then (f + fP )(u, v ) = 0. Else,
≤cf (v ,u)=f (u,v )
z }| {
(f + fP )(u, v ) = f (u, v ) + fP (u, v ) − fP (v , u) ≥ fP (u, v ) ≥ 0.
(f + fP )(u, v ) = f (u, v ) + fP (u, v ) − fP (v , u) ≤ f (u, v ) + fP (u, v ) ≤ c(u, v ).
| {z }
≤cf (u,v )=c(u,v )−f (u,v )

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 10
Augmenting Paths
Proof (Cont.)
P P
Flow conservation: ∀u ∈ V \ {s, t} : (f + fP )(u, v ) = (f + fP )(v , u).
v ∈V v ∈V
P P
(f + fP )(u, v ) = f (u, v ) + fP (u, v ) − fP (v , u)
v ∈V v ∈V
P P P
= f (u, v ) + fP (u, v ) − fP (v , u)
v ∈V
P v ∈V
P v ∈V
P
= f (v , u) + fP (v , u) − fP (u, v )
v ∈V
P v ∈V v ∈V P
= f (v , u) + fP (v , u) − fP (u, v ) = (f + fP )(v , u).
v ∈V v ∈V

Value of flow f + fP :
P P
|f + fP | = (f + fP )(s, v ) − (f + fP )(v , s)
v ∈V
P v ∈V P
= f (s, v ) + fP (s, v ) − fP (v , s) − f (v , s) + fP (v , s) − fP (s, v )
+
v ∈N (s)
P P v ∈N − (s)
= f (s, v ) − f (v , s)
v ∈N + (s) v ∈N − (s)
P P P P
+ fP (s, v ) + fP (s, v ) − fP (v , s) − fP (v , s)
+
v ∈N − (s) v ∈N + (s) v ∈N − (s)
Pv ∈N (s)
P
= f (s, v ) − f (v , s) + fP (s, v ) − fP (v , s) = |f | + |fP |
v ∈V v ∈V

N + (s), N − (s) : out-/in-neighbors of s. Note that N + (s) ∩ N − (s) = ∅ as G simple.

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 11
Ford-Fulkerson Algorithm

Augment(Gf , P) FordFulkerson(G)
cf (P) ← mine on P cf (e) for all e ∈ E do f (e) ← 0
for all e on P do construct Gf
if e ∈ E then while ∃P = s ; t in Gf do
f (e) ← f (e) + cf (P) Augment(Gf , P)
else f (e rev ) ← f (e rev ) − cf (P) update Gf

u v
10
4
12
10
s t
4 4
2

6 2
4
w x
4 |f | = 16

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 12
Ford-Fulkerson Algorithm

Augment(Gf , P) FordFulkerson(G)
cf (P) ← mine on P cf (e) for all e ∈ E do f (e) ← 0
for all e on P do construct Gf
if e ∈ E then while ∃P = s ; t in Gf do
f (e) ← f (e) + cf (P) Augment(Gf , P)
else f (e rev ) ← f (e rev ) − cf (P) update Gf

2
u v
8
2
12
10
s 2 t
2 2
8 4
6
w x
4 |f | = 18

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 12
Flows and Cuts

Lemma (Flow Value)

If f is a flow in a network G = (V , E , c, s, t) and (S, T ) an s-t cut, then f ’s value equals the
net flow across the cut, i. e. ,
P P
|f | = f (u, v ) − f (v , u)
u∈S,v ∈T u∈S,v ∈T

P P
Proof. |f | = f (s, v ) − f (v , s)
v ∈V v ∈V
P P P P
= f (s, v ) − f (v , s) + f (u, v ) − f (v , u)
v ∈V v ∈V u∈S\{s} v ∈V
| {z }
=0 (flow conservation)
P P P P
= f (u, v ) − f (v , u)
u∈S v ∈V u∈S v ∈V
PP P P PP P P
= f (u, v ) + f (u, v ) − f (v , u) − f (v , u)
u∈S v ∈S u∈S v ∈T u∈S v ∈S u∈S v ∈T
P P P P
= f (u, v ) − f (v , u).
u∈S v ∈T u∈S v ∈T

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 13
Weak Duality

Theorem (Weak Duality)

If f is a flow in a network G = (V , E , c, s, t) and (S, T ) an s-t cut, then
|f | ≤ c(S, T ).

Proof.
By the Flow Value lemma,
X X X X
|f | = f (u, v ) − f (v , u) ≤ f (u, v ) ≤ c(u, v ) = c(S, T ).
u∈S,v ∈T u∈S,v ∈T u∈S,v ∈T u∈S,v ∈T

Corollary (Weak Duality)

Let f be a flow in a network G = (V , E , c, s, t) and (S, T ) an s-t cut. If |f | = c(S, T ), then f
is a maximum flow and (S, T ) is a minimum cut.
Proof.
Let f ′ be any flow and let (S ′ , T ′ ) be any s-t-cut. By the Weak Duality theorem,

|f ′ | ≤ c(S, T ) = |f | ≤ c(S ′ , T ′ ).

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 14
Max-Flow Min-Cut Theorem

Theorem (Max-Flow Min-Cut)

If f is a flow in a network G = (V , E , c, s, t), then the following conditions are equivalent:
(i) There is an s-t cut (S, T ) with c(S, T ) = |f |.
(ii) f is a maximum flow in G.
(iii) Gf contains no augmenting paths.
Proof.
(i) ⇒ (ii) Follows by the Weak Duality corollary.
(ii) ⇒ (iii) Suppose Gf contains an augmenting path P. Then, |f | can be increased by |fP | > 0, so f is
not a maximum flow, a contradiction.
(iii) ⇒ (i) Let S be the set of all vertices reachable from s in Gf and T = V \ S. Then, s ∈ S, t ∈ T ,
and (S, T ) is an s-t-cut. For any (u, v ) ∈ S × T , cf (u, v ) = 0, i.e., (1) if e = (u, v ) ∈ E , then
f (e) = c(e) and (2) if e = (v , u) ∈ E , then f (e) = 0. By the Flow Value lemma,
P P P
|f | = f (u, v ) − f (v , u) = c(u, v ) − 0 = c(S, T ).
u∈S,v ∈T u∈S,v ∈T u∈S,v ∈T
| {z } | {z }
apply (1) apply (2)

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 15
Strong Duality

Theorem (Strong Duality)

Let f ∗ be a maximum s-t flow and let (S ∗ , T ∗ ) be a minimum s-t cut. Then, |f ∗ | = c(S ∗ , T ∗ ).

Proof.
We show the claim in two steps:
“≤”: By the Weak Duality theorem, |f | ≤ c(S, T ) for any s-t flow f and any s-t cut (S, T ).
Hence, it holds in particular that |f ∗ | ≤ c(S ∗ , T ∗ ).
“≥”: By the Max-Flow Min-Cut theorem, there is an s-t cut (S, T ) with c(S, T ) = |f ∗ |.
Hence, |f ∗ | = c(S, T ) ≥ c(S ∗ , T ∗ ), as (S ∗ , T ∗ ) is minimum.

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 16
Ford-Fulkerson Algorithm: Correctness

▶ If the Ford-Fulkerson algorithm terminates, the residual graph contains no

augmenting path.
▶ By the Max-Flow Min-Cut theorem, the computed flow is maximum.
Does the algorithm always terminate?
A bad example . . .

u 10
0 0 00
000 00
10 0

s 10 1 t
0
00 00
00 00
0 10

v
...
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 17
Ford-Fulkerson Algorithm: Correctness

▶ If the Ford-Fulkerson algorithm terminates, the residual graph contains no

augmenting path.
▶ By the Max-Flow Min-Cut theorem, the computed flow is maximum.
Does the algorithm always terminate?
A bad example . . .

u 10
9 00
999 00
99 0
1
s 10 1 t
0 9
00
0 9 99
0 99
1
v
...
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 17
Ford-Fulkerson Algorithm: Termination

Theorem
Let G = (V , E , c, s, t) be a flow network and let |f ∗ | be the value of a maximum flow. If all
capacities in G are integral, the Ford-Fulkerson algorithm terminates in O(m · |f ∗ |) time.

Proof.
▶ Finding an s-t path in Gf , augmenting FordFulkerson(G)
for all e ∈ E do f (e) ← 0
the flow on it, and updating Gf takes construct Gf
O(n + |Ef |) = O(|Ef |) = O(m) time. while ∃P = s ; t in Gf do
▶ Each iteration of the while loop Augment(Gf , P)
update Gf
takes O(m) time.
▶ In each iteration, the flow increases by at least one unit.
⇒ There are at most |f ∗ | iterations.
▶ The initialization takes O(m) time.
⇒ The algorithm runs in O(m · |f ∗ |) time.

Note: There are networks where the Ford-Fulkerson algorithm may fail to terminate.
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 18
Ford-Fulkerson Algorithm: Termination
There are networks where the Ford-Fulkerson algorithm may fail to terminate:
√
Let M ≥ 4 and r = 5−12 ≈ 0.618. (Note: 1 − r = r 2 )
Consider the network on the right along with the following augmenting paths:
u
P0 = ⟨s, w , v , t⟩ |f | = 1 r M
P1 = ⟨s, u, v , w , x , t⟩ |f | = 1 + r M
v
P2 = ⟨s, w , v , u, t⟩ |f | = 1 + 2r
P3 = P1 = ⟨s, u, v , w , x , t⟩ |f | = 1 + 2r + r2 s M
M 1 t
P4 = ⟨s, x , w , v , t⟩ |f | = 1 + 2r + 2r 2 w
P5 = P1 = ⟨s, u, v , w , x , t⟩ |f | = 1 + 2r + 2r 2 + r 3 M
P6 = P2 = ⟨s, w , v , u, t⟩ |f | = 1 + 2r + 2r 2 + 2r 3 1 M
x

P0 (P1 , P2 , P1 , P4 )∗ is an infinite sequence of augmenting paths.

∞
r i = 1 + 2r < 5, whereas the maximum flow is 2M + 1.
P
The flow value converges to 1 + 2
i=1
Uri Zwick. The smallest networks on which the Ford-Fulkerson maximum
flow procedure may fail to terminate. TCS 148(1), 1995, pp. 165–170.

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 19
Choosing Augmenting Paths
On a network with integral capacities and maximum edge capacity C , the
Ford-Fulkerson algorithm runs in time O(m · |f ∗ |) ⊆ O(m · n · C ).

Are there clever(er) ways to choose augmenting paths?

▶ Look for paths with large residual capacity ⇒ O(m2 · log C )
▶ Look for shortest paths (w. r. t. the number of edges)
Known as Edmonds-Karp algorithm.
⇒ O(m2 · n)
▶ Look for all shortest paths “at once”, before updating the flow and recomputing Gf ,
so-called “blocking flows” Dinitz algorithm
⇒ O(n2 · m)

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 20
Level Graph
▶ Let G = (V , E ) be a graph and s ∈ V .
▶ For each vertex v ∈ V , let l(v ) denote v ’s distance from s (the number of edges
on a shortest path s ; v ).
▶ The level graph G L = (V , E L ) of G is the subgraph of G that contains only the
edges E L = {(u, v ) ∈ E | l(u) + 1 = l(v )}.
▶ P = s ; v is a path in G L ⇔ P is a shortest path in G
▶ Can be computed via breadth-first search in O(n + m).

u v

s t

w x
Levels: l=0 l=1 l=2 l=3

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 21
Blocking Flows
Edmonds-Karp needs O(n · m) augmentations. Can we do better than that?
There are networks that require Θ(n · m) augmentations.
⇒ Try to speed up the augmentation process!

Let f be a flow in a network G = (V , E , c, s, t).

A blocking flow is a flow f ′ in Gf such that each path s ; t in GfL contains at least one
bottleneck edge.
4/4
u v
0 4/
/1 10
10

6/
s 2 6 t

4/
10 8 /1
0
4/9 10
w x

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 22
Blocking Flows

How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.

4
u v
10
10

s t
8
10
10
9
w x

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 23
Blocking Flows

How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.

4
u v
10
10

s t
8
10
10
9
w x

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 23
Blocking Flows

How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.

u v
6 6

s t

10 8
10
9
w x

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 23
Blocking Flows

How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.

u v
6

s t
2
10 4
9
w x

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 23
Blocking Flows

How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.

u v
6

s t
2
6
5
w x

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 23
Blocking Flows

How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.

u v
6

s t

6
w

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 23
Blocking Flows

How to Find a Blocking Flow

0 Initialization: Construct the level graph GfL .
1 Advance: Starting from s, follow edges of GfL as in a depth-first search.
2 Augment: If reach t, augment flow along s ; t, remove bottleneck edges, and start again
from s.
3 Retreat: If get stuck at vertex v , remove v from GfL and go back to previous vertex.

u v
6

s t

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 23
Dinitz Algorithm

BlockingFlow(Gf )
Dinitz(G) construct level graph GfL of Gf
for all e ∈ E do f (e) ← 0 P ← ⟨⟩; v ← s; blocking ← false
while !blocking do
construct Gf
if v = t then ▷ augment
while ∃s ; t in Gf do
Augment(Gf , P)
BlockingFlow(Gf )
remove bottleneck edges from GfL
update Gf
P ← ⟨⟩; v ← s
else if ∃(v , w ) ∈ EfL then ▷ advance
P ← P + (v , w ); v ← w
else ▷ retreat
computation of a blocking flow, if v = s then
including update of Gf blocking ← true
=
b else
remove v from GfL
“phase” remove last edge (u, v ) from P
v ←u

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 24
Dinitz Algorithm: Analysis

Lemma
The Dinitz algorithm uses at most O(n) phases.

Proof.
After each phase, the distance from s to t increases strictly. As the maximum distance is n − 1, there
can be at most O(n) phases.

Lemma
Each phase in the Dinitz algorithm takes at most O(nm) time.

Proof.
In each phase . . .
. . . the computation of GfL via BFS takes O(m) time,
. . . there are at most m augmentations (each augmenting path has at least one bottleneck edge,
which is then removed),
. . . there are at most n retreats,
. . . there are at most n advances before an augmentation or a retreat, i. e. , at most n · m advances in
total.
Hence, each phase can be implemented in O(n · m) time.
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 25
Dinitz Algorithm: Analysis

Theorem
The Dinitz algorithm computes a maximum flow in time O(n2 m).

Proof.
There are at most O(n) phases and each phase can be implemented in O(n · m) time. Hence, the
algorithm runs in O(n2 m) time.

Using dynamic trees, each phase can be implemented in O(m log n) time.
Theorem
The Dinitz algorithm with dynamic trees computes a maximum flow in time O(n · m log n).

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 26
Maximum Flow Algorithms
Year Method Running time By
1956 augmenting paths O(nmC ) Ford & Fulkerson
1969 shortest augmenting paths O(nm2 ) Edmonds & Karp
1970 blocking flows O(n2 m) Dinitz
1973 capacity scaling O(nm log C ) Dinitz
1974 blocking flows + preflow O(n3 ) Karzanov
1980 blocking flows O(nm log2 n) Galil & Naamad
1983 blocking flows + dynamic trees O(nm log n) Sleator & Tarjan
1986 push-relabel O(n3 ) Goldberg & Tarjan
2
push-relabel + dynamic trees O(nm log nm )
√
1989 highest-label push-relabel O(n2 m) Cheriyan & Maheshwari
2 √
1998 binary blocking flows O(min{n 3 , m} Goldberg & Rao
2
·m log nm log C )
2013 compact networks O(nm) Orlin
√
2014 interior-point methods Õ(m n log C ) Lee & Sidford
2016 electrical flows Õ(m10/7 C 1/7 ) Mądry
2022 min-ratio cycles O(m1+o(1) log C ) Chen, Kyng, Liu, Peng, Gutenberg, Sachdeva
n = |V |, m = |E |, C = maximum edge capacity (integral)
Note: This list is incomplete (by far)!
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 27
Maximum Bipartite Matching

A matching in an undirected graph G = (V , E ) is a

set M ⊆ E such that every vertex is the end vertex
of at most one edge in M .

An undirected graph G = (V , E ) is bipartite if its

vertex set can be partitioned such that no edge has
both end vertices in the same partition, i. e. ,
V = V1 ⊔ V2 and E ⊆ V1 × V2 .

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 28
Maximum Bipartite Matching

Maximum Bipartite Matching

Given: undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 )
Wanted: a matching M of maximum cardinality

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 29
Maximum Bipartite Matching

Maximum Bipartite Matching ⇒ Maximum Flow

Given: undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 )
Construct a flow network G ′ from G as follows:
▶ Add a source vertex s and a sink vertex t.
▶ Add an edge from s to every vertex in V1 with capacity 1.
▶ Add an edge from every vertex in V2 to t with capacity 1.
▶ Direct all original edges from V1 to V2 and set their capacity to 1.

1
1 1
1
1
1 1
1
s 1 t
1 1
1
1 1

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 30
Maximum Bipartite Matching

Theorem
An undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 ) has a matching of cardinality k if
and only if the corresponding flow network G ′ has a flow of size k.

Proof: “⇒”.
▶ Let M be a matching in G with |M| = k.
▶ In G ′ , set f (s, u) = f (u, v ) = f (v , t) = 1 if {u, v } ∈ M and f (e) = 0 for all other edges.
▶ Then, f is a flow in G ′ and |f | = k.

1/1

0/1 1/

1
1/

0/
1

1
0/1 0/1
1/1
s 1/1 t
1/1 1
1/
1

1/
1/

1
0/1

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 31
Maximum Bipartite Matching

Theorem
An undirected, bipartite graph G = (V1 ⊔ V2 , E ⊆ V1 × V2 ) has a matching of cardinality k if
and only if the corresponding flow network G ′ has a flow of size k.
Proof: “⇐”.
▶ Let f be a flow in G ′ with |f | = k.
▶ All capacities in G ′ are integral, so f is integral (in fact, f is 0-1).
▶ Let M = {{u, v } ∈ E | f (u, v ) = 1}. By construction, every vertex in G is the end vertex
of at most one edge in M, so M is a matching.
▶ Due to flow conservation, |f | = u∈V f (s, u) = u∈V ,v ∈V f (u, v ) = |M| = k.
P P
1 1 2

1/1

0/1 1/
1
1/

0/

1
1

0/1 0/1
1/1
s 1/1 t
1/1 1
1/
1
1/

1/
1

0/1

Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 32
Maximum Bipartite Matching

Algorithms:
Year Method Running time By
1956 augmenting paths O(nm) Ford & Fulkerson
√
1973 blocking flows O( nm) Hopcroft & Karp, Karzanov
2004 fast matrix multiplication O(n2.376 ) Mucha & Sankowski
2016 electrical flows Õ(m10/7 ) Mądry
n = |V |, m = |E |
Note: This list is very likely incomplete.

Real-world applications:
All kinds of assignment problems: agents & tasks, machines & jobs, hospital &
patients, kidney donors . . .
Subgraph isomorphism
Computer vision (e.g. following/recognizing objects between frames, after blurring, . . . )
...
Kathrin Hanauer, Gramoz Goranci Algorithms and Data Structures 2: Maximum Flow 33