Algorithms II (CS31005) Partha Bhowmick

Autumn 2012 CSE, IIT Kharagpur

1 Flow Networks

If you optimize everything, you will al-

ways be unhappy.
— Donald Knuth

A flow network G = (V, E) is a directed graph in which each edge (u, v) ∈ E has a capacity c(u, v) ≥ 0.
If (u, v) 6∈ E, then c(u, v) = 0. Two special vertices, namely a source s, and a sink t, are considered
from V .
A flow in G is a real-valued function f : V 2 → R that satisfies the following necessary and sufficient
properties:

1. Capacity constraint: f (u, v) ≤ c(u, v) ∀(u, v) ∈ V 2 .

2. Skew symmetry: f (u, v) = −f (v, u) ∀(u, v) ∈ V 2 .
P
3. Flow conservation: f (u, V ) = f (u, v) = 0 ∀u ∈ V r {s, t}.
v∈V

The net flow from a vertex u to a vertex v is the quantity f (u, v) that can be positive, negative, or zero.
The value of f in G is defined as X
|f | = f (s, V ) = f (s, v). (1)
v∈V

Maximum-flow problem: Maximize |f | for a given G.

1.1 Properties of a flow network

1. f (u, u) = 0 ∀u ∈ V
Proof: From skew symmetry, for v = u, f (u, u) = −f (u, u). 

2. f (V, u) = 0 ∀u ∈ V r {s, t}
Proof: From skew symmetry, for all (u, v) ∈ V 2 , f (u, v) = −f (v, u), or,
P P
f (u, v) = − f (v, u),
u∈V u∈V
or, f (V, v) = −f (v, V ) = 0∀v ∈ V r {s, t} (by flow conservation). 

1
Lemma 1.1 (Subgraph flow)

1. f (X, X) = 0 for X ⊆ V
Proof: From skew symmetry, f (u, v) = −f (v, u) for all (u, v) ∈ V 2 ,
2
or, fP
(u, v)
P= −f (v, u) for
P all
P(u, v) ∈ X ,
or, f (u, v) = (−f (v, u)),
u∈X v∈X u∈X v∈X
or, f (X, X) = −f (X, X). 

2. f (X, Y ) = −f (Y, X) for X, Y ⊆ V

Proof: From skew symmetry, f (u, v) = −f (v, u) for all (u, v) ∈ V 2 ,
or, fP
(u, v)
P= −f (v, u) P for all
P (u, v) ∈ X × Y ,
or, f (u, v) = (−f (v, u)),
u∈X
P v∈Y P u∈X v∈Y
or, f (u, Y ) = (−f (Y, u)), or, f (X, Y ) = −f (Y, X). 
u∈X u∈X

3. f (X ∪ Y, Z) = f (X, Z) + f (Y, Z) and f (Z, X ∪ Y ) = f (Z, X) + f (Z, Y )

for X, Y, Z ⊆ V, X ∩ Y = ∅
P P P
Proof: f (X ∪ Y, Z) = f (u, Z) = f (u, Z) + f (u, Z) [since X ∩ Y = ∅]
u∈X∪Y u∈X u∈Y
= f (X, Z) + f (Y, Z).
The other proof is similar. 

4. |f | = f (V, t)
Proof: |f | = f (s, V ) = f (V, V ) − f (V r {s}, V ) [by previous property]
= f (V, V r {s}) [since f (V, V ) = 0]
= f (V, t) + f (V, V r {s, t}) [by previous property]
= f (V, t) [since f (V, V r {s, t}) = 0].
How f (V, V r {s, t}) = 0? By flow conservation, f (u, V ) = 0 for every vertex u ∈ V r {s, t}.
Hence summing up those f (u, v)s for u ∈ V r{s, t}, we get f (V r{s, t}, V ) = 0, or, f (V, V r{s, t}) =
0 [by Property 2 of this lemma]. 

1.2 Ford-Fulkerson Algorithm

It starts with f (u, v) = 0 ∀(u, v) ∈ V 2 . Iteratively, it increases the flow by finding an augmenting path
from s to t along which more flow can be pushed.
Given an existing flow f in G, the maximum amount of additional flow that can be still pushed from any
vertex u ∈ V to any vertex v ∈ V is defined as the residual capacity of (u, v), given by

cf (u, v) = c(u, v) − f (u, v). (2)

Example: Let c(u, v) = 10, c(v, u) = 0. Then f (u, v) = 6 yields cf (u, v) = 10 − 6 = 4 and cf (v, u) =
0 − (−6) = 6.
The residual network of G induced by f is Gf = (V, Ef ), where Ef = {(u, v) ∈ V 2 : cf (u, v) > 0}.
The edges in Ef are called residual edges. We have the following lemma on the size of Ef .

Lemma 1.2 |Ef | ≤ 2|E|.

Proof: (u, v) ∈ Ef only if (i) (u, v) ∈ E or (ii) (u, v) 6∈ E but (v, u) ∈ E.
Hence the proof. 

2
From Gf , we can augment a larger flow in G, as stated in the following lemma.

Lemma 1.3 If f is a flow in G and f 0 is a flow in Gf , then f + f 0 is a flow in G whose value is

|f + f 0 | = |f | + |f 0 |.
Proof: We first prove the three flow properties for f + f 0 on G.
Skew symmetry: For all (u, v) ∈ V 2 , (f + f 0 )(u, v) = f (u, v) + f 0 (u, v) = −f (v, u) − f 0 (v, u) = −(f +
f 0 )(v, u).
Capacity constraints: For all (u, v) ∈ V 2 , (f + f 0 )(u, v) = f (u, v) + f 0 (u, v) ≤ f (u, v) + c(u, v) − f (u, v)
[since f 0 (u, v) ≤ cf (u, v) = c(u, v) − f (u, v)], or, (f + f 0 )(u, v) ≤ c(v, u).
Flow conservation: For all u ∈ (V r {s, t}), (f + f 0 )(u, V ) = f (u, V ) + f 0 (u, V ) = 0 + 0 = 0.
Now, |f + f 0 | = (f + f 0 )(s, V ) = f (s, V ) + f 0 (s, V ) = |f | + |f 0 |, which completes the proof. 

From Lemma 1.3, it’s clear that if we get an augmenting path p in Gf , and find its residual capacity ,
given by
cf (p) = min{cf (u, v) : (u, v) ∈ p},
then fp = cf (p) is a flow in Gf , which augments the flow in G from f to f + fp . Iteratively, f + fp induces
another residual network, and so on. When shall it converge to yield the max flow? It’s obviously when
the residual network contains no augmenting path. The Max-flow Min-cut Theorem answers this,
which is explained next.
12/12 A cut(S, T ) of G(V, E) is a partition of V into S and T = V rS
a b
such that s ∈ S and t ∈ T . If f is a flow in G then the net flow
6

15
/1

/2

across this cut is defined as f (S, T ), and its capacity is c(S, T ).

11

In the figure aside, f (S, T ) = 12 − 4 + 11 = 19, and its capacity

1/4

7/7

s
10

t is c(S, T ) = 12 + 14 = 26.
9
4/

Note: f (S, T ) consists of all flows from S to T , but c(S, T )

8/

4
4/
13

only the positive capacities.

c 11/14 d P P P P
f (S, T ) = f (u, v), c(S, T ) = c(u, v).
S T u∈S v∈T u∈S v∈T

Lemma 1.4 (Flow-cut lemma) If f be any flow in G, then for any cut (S, T ) of G, f (S, T ) = |f |.
Proof: Based on the properties 1 and 3 of Lemma 1.1.

f (S, T ) = f (S, V ) − f (S, S) [By Lemma 1.1-3, f (S, V r S) = f (S, V ) − f (S, S)]
= f (S, V ) [By Lemma 1.1-1, f (S, S) = 0]
= f (s, V ) + f (S r {s}, V ) [By Lemma 1.1-3]
By Lemma 1.1-3. Since t 6∈ S, we get S r {s, t} = S r {s}.
= f (s, V ) Thus, by flow conservation, f (u, V ) = 0 ∀u ∈ S r {s}, which sums to
f (S r {s}, V ) = 0.
= |f |. 

From Flow-cut lemma (Lemma 1.4), it’s evident that |f | ≤ c(S, T ) for any cut S(, T ) . This gives Max-
flow Min-cut Theorem, stated as follows.

Theorem 1.5 (Max-flow Min-cut Theorem) If f is a flow in G, then the following conditions are
equivalent.

1. f is a max flow in G.
2. Gf contains no augmenting path.
3. |f | = c(S, T ) for a cut (S, T ) having minimum capacity (min-cut).

Proof: (1) ⇒ (2) : By contradiction. If Gf has some augmenting path p, then some more flow f 0 can be
shipped through p, resulting to increase in flow from f to f 0 .
(2) ⇒ (3) : Define a cut as follows.
S = {u ∈ V : there exists a path from s to u in Gf }, and T = V r S.

3
 Algorithm 1: Ford-Fulkerson(G, s, t).
1 for each (u, v) ∈ E do
2 f (u, v) ← f (v, u) ← 0
3 while ∃ p(s t) ∈ Gf do
4 cf (p) ← min{cf (u, v) : (u, v) ∈ p}
5 for each (u, v) ∈ p do
6 f (u, v) ← f (u, v) + cf (p)
7 f (v, u) ← −f (u, v)

a a a

12 7 9 12 7 9 12 7 9

9 9 13
10 8 10 8 4/10 4/8
s b c t s b c t s b c t
4 4 4 4

min cf
8 3 10 8 3 10 8 3 10

d d d
(a) (b) (c)

Figure 1: (a) A flow network G with its edge capacities. (b) An augmenting path p = hs, b, c, ti with
c(p) = min{c(s, b), c(b, c), c(c, t)} = 4. (c) The residual network Gf after augmenting a flow of value |f | =
4 through p. Note how c(b, s) changes 0 to 4, as c(b, s) = 0 − (−|f |) = 4 after the augmentation. Similar
is the case of c(t, c). The residual capacity of (c, b) also gets changed to 9 − (−4) = 13.

Now, for each (u ∈ S, v ∈ T ), we have f (u, v) = c(u, v); for, otherwise (u, v) ∈ Ef , which implies v ∈ S—
a contradiction. Hence, by Flow-cut lemma (Lemma 1.4), |f | = f (S, T ) = c(S, T ), which is a min-cut as
its capacity is minimum and all other cuts of G have c ≥ |f |.
(3) ⇒ (1) : Since |f | ≤ c(S, T ) for any cut (S, T ) as explained earlier in consequence of Flow-cut lemma
(Lemma 1.4), the condition f = c(S, T ) implies that f is a max flow. 

The basic Ford-Fulkerson algorithm: It applies BFS first on G and then iteratively on Gf with s as
the start vertex to find an augmenting path p (from s to t); see Algo 1 and Fig. 1. If all the edges of G
have integer (or ‘integer-able’) capacities—as mostly found in practice, then Algo 1 may iterate as many
as |f | times, thus consuming O(E|f |) time in the worst case (O(E) time for Steps 1–2 and O(E) × |f |
for the while loop (Steps 3–7)). A typical example is given in Fig. 2. As |f | may be unusually large, the
algorithm is not ready to get explained in terms of an efficient time complexity.

Improvement: By Edmonds-Karp algorithm 1 , irrespective of integer or non-integer capacities. It

finds the shortest path from s to t in Gf , considering all its edges with unit weight. Its O(V E 2 ) time
complexity can be explained by the following sequence of arguments. (See Cormen et al.: pp. 597–599
for details.)

1. Since G has E edges, any residual graph down the iterations of while loop has at most 2E = O(E)
edges (Lemma 1.2).
2. Each augmenting path p can be found as a shortest path by BFS in O(E) time, and every time
at least one of the O(E) edges lying on p becomes critical 2 and disappears in the residual graph
used in the next iteration.
3. For each vertex v ∈ V r {s, t}, its shortest-path distance δf (s, v) from s in Gf increases monotoni-
cally (not strictly always) with successive flow augmentations.
1 Jack Edmonds and Richard M. Karp (1972). Theoretical improvements in algorithmic efficiency for network flow

problems. Journal of the ACM 19(2): 248–264.

2 An edge of the augmenting path p whose residual capacity equals the flow of p.

4
 a a

99
0

10

10
10

0
1
s 1 t s 1 t
1

10

10
10
0

0
b b

99
Figure 2: Two iterations of the basic Ford-Fulkerson algorithm. In each iteration, the augmenting path
(shown in bold) is not the shortest path ((s, a, t) or (s, b, t)) from s to t in G or Gf with unit-weight
edges and the flow capacity of the augmenting path is 1. Had the augmenting paths been (s, a, t) and
(s, b, t) in the first two iterations, we could have obtained the max-flow |f | = 100 + 100 = 200 in just two
iterations! In fact, Edmonds-Karp version gets it in two iterations by using the two shortest paths.

4. At most O(V E) flow augmentations are required.

Reason: Each of O(E) edges becomes critical at most O(V ) times.

1.3 Maximum Bipartite Matching

Matching: A matching (or independent edge set) in an undirected graph G(V, E) is a subset of
edges M ⊆ E in which no two edges share a common vertex. A vertex v ∈ V is said to be matched by
M if some edge of M is incident on v; otherwise, v is unmatched .
M is said to be a maximal matching if no more edge can be added from E r M to M ; that is, M is
maximal if it is not a proper subset of any other matching in G (Fig. 3).
If the matching M has maximum cardinality, then it is called a maximum matching (Fig. 3). Note
that every maximum matching is always maximal, but not the reverse. A perfect matching (1-factor
matching) is a matching which matches all vertices of G. that is, every vertex of the graph is incident to
exactly one edge of the matching.

Figure 3: Maximal matching (left) versus maximum matching (right). The maximum matching here is
also a perfect matching. Edges in the matching are highlighted in gray.

Maximum bipartite matching: A bipartite graph is an undirected graph G(V, E) in which V can
be partitioned into two sets, X and Y , such that each edge of E has one vertex in X and the other vertex
in Y . Since a matching M in any graph G(V, E) is a subset of E, each edge of M for a bipartite matching
naturally has one vertex in X and the other vertex in Y .
We can use the Ford-Fulkerson algorithm to find a maximum matching in a bipartite graph G(V, E) with
the partition V = X ∪ Y . For this, we first construct the flow network G0 = (V 0 , E 0 ) from G as follows.
Take a source s and a sink t, and define X 0 = X ∪ {s}, Y 0 = Y ∪ {t} so that V 0 = V ∪ {s, t}; define
E 0 = {(s, u) : u ∈ X} ∪ {(u, v) : u ∈ X, v ∈ Y, (u, v) ∈ E} ∪ {(v, t) : v ∈ Y } (all directed edges). Assign
unit capacity to each edge in E 0 . The max-flow in G0 will be a positive integer that equals the cardinality
of maximum matching in G. It’s based on the Lemma 1.6 and Integrality theorem (Theorem 1.7).

Lemma 1.6 M is a matching in G if and only if there is a flow f in G0 such that |f | = |M |.

Proof: To show that a matching (whether max or not) M in G corresponds to a flow f in G0 , define f as
follows. For each (u, v) ∈ M , assign f (s, u) = f (u, v) = f (v, t) = 1 and f (u, s) = f (v, u) = f (t, v) = −1.
For each (u, v) ∈ E 0 rM , assign f (u, v) = 0. The flow properties (capacity constraint, skew symmetry, and
flow conservation) can be easily verified for each such unit-value flow from s to t containing (u, v) ∈ M .
The net flow across the cut (X 0 , Y 0 ) is equal to |M |, and so |M | = |f | by flow-cut lemma (Lemma 1.4).

5
 X Y X0 Y0
x1 y1 x1 y1

x2 y2 x2 y2

x3 y3 s x3 y3 t
x4 y4 x4 y4

x5 y5 x5 y5
(a) (b)

Figure 4: (a) A bipartite graph G(V, E) with V = X ∪ Y as the bipartite set of vertices. (b) The flow
network G0 constructed from G.

Conversely, if f is an integer-valued flow in G0 , then define M = {(u, v) : u ∈ X, v ∈ Y, f (u, v) = 1}.

Since each u ∈ X has one entering edge (s, u) with c(s, u) = 1, by Integrality theorem, f (s, u) ∈ {0, 1}.
Hence, by flow conservation, f (u, Y ) ∈ {0, 1}, which implies that at most one edge leaving from u is
included in M . A symmetric argument shows that at most one incoming edge to each v ∈ Y has a 1-unit
flow and included in M . Thus, M is a valid matching in G. To show |M | = |f |, we use the just-proven
fact that f (u, v) = 1 iff (u, v) ∈ M . Hence,
|M | = f (X, Y )
= f (X, V 0 ) − f (X, s) − f (X, X) − f (X, t)
By flow conservation, f (X, V 0 ) = 0;
by skew symmetry, f (X, s) = −f (s, X);
= 0 + f (s, X) − 0 − 0
by Subgraph Flow (Lemma 1.1): Property 1, f (X, X) = 0;
f (X, t) = 0, as there is no edge from X to t.
= f (s, V 0 ) [Since there is no edge from s to V 0 r X]
= |f |. 

Result: As M ⇔ f with |M | = |f |, we get max{|M |} ⇔ max{|f |}.

Theorem 1.7 (Integrality theorem) If the edge capacities of a flow network are integer-valued, then
by Ford-Fulkerson algorithm, the flows across all edges, and hence the max flow f , are all integer-valued.
Proof: By induction on the number of iterations. 

Alternating nature of augmenting paths: If a matching M is not maximum in G, then the corre-
sponding flow f in G0 is also not maximum, and so there is an augmenting path p in the residual network
G0f (Fig. 5). Some edges in this path p are backward (i.e., directed from Y to X) and some forward
(directed from X to Y ), although initially all edges in G0 were directed from X to Y ! Augmenting paths
therefore alternate between edges used backward and forward, and hence also called alternating paths
in the context of graph matching. The effect of this augmentation is to take the backward edges out of
the matching and replace them with the forward edges. Because the augmenting path goes from s to t,
there is always one more forward edge than backward edge, thereby increasing the matching size by one.

X Y X Y X Y
x1 y1 x1 y1 x1 y1
x2 y2 x2 y2 x2 y2
x3 y3 x3 y3 x3 y3
x4 y4 x4 y4 x4 y4
x5 y5 x5 y5 x5 y5
(a) (b) (c)

Figure 5: (a) A bipartite graph with a matching M (bold edges). (b) The augmenting path (dashed) in
the residual graph. (c) The maximum matching (bold edges) obtained by the augmentation.

6
Books

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (1990). Introduction
to Algorithms. MIT Press (Indian Reprint by PHI).
2. Jon Kleinberg and Éva Tardos (2006). Algorithm Design. Pearson Education (India).