Chapter 7

Network Flow

Slides by Kevin Wayne.

Copyright © 2005 Pearson-Addison Wesley.
All rights reserved.

1
7.5 Bipartite Matching
 Bipartite Matching

Bipartite matching.
■ Input: undirected, bipartite graph G = (L ∪ R, E).
■ M ⊆ E is a matching if each node appears in at most edge in M.
■ Max matching: find a max cardinality matching.

1 1'

2 2' matching
1-2', 3-1', 4-5'

3 3'

4 4'

L 5 5' R
4
 Bipartite Matching

Bipartite matching.
■ Input: undirected, bipartite graph G = (L ∪ R, E).
■ M ⊆ E is a matching if each node appears in at most edge in M.
■ Max matching: find a max cardinality matching.

1 1'

2 2' max matching

1-1', 2-2', 3-3' 4-4'

3 3'

4 4'

L 5 5' R
5
 Bipartite Matching

Max flow formulation.

■Create digraph G' = (L ∪ R ∪ {s, t}, E' ).
■Direct all edges from L to R, and assign infinite (or unit) capacity.
■Add source s, and unit capacity edges from s to each node in L.
■Add sink t, and unit capacity edges from each node in R to t.

G' 1 ∞ 1'

1 1
2 2'

s 3 3' t

4 4'

L 5 5' R

6
 Bipartite Matching: Proof of Correctness

Theorem. Max cardinality matching in G = value of max flow in G'.

Pf. ≤
■ Given max matching M of cardinality k.
■ Consider flow f that sends 1 unit along each of k paths.
■ f is a flow, and has cardinality k. ▪

1 1' 1 ∞ 1'

1 1
2 2' 2 2'

3 3' s 3 3' t

4 4' 4 4'

G G'
5 5' 5 5'

7
 Bipartite Matching: Proof of Correctness

Theorem. Max cardinality matching in G = value of max flow in G'.

Pf. ≥
■ Let f be a max flow in G' of value k.
■ Integrality theorem ⇒ k is integral and can assume f is 0-1.
■ Consider M = set of edges from L to R with f(e) = 1.
– each node in L and R participates in at most one edge in M
– |M| = k: consider cut (L ∪ s, R ∪ t) ▪

1 ∞ 1' 1 1'

1 1
2 2' 2 2'

s 3 3' t 3 3'

4 4' 4 4'

G' G
5 5' 5 5'
8
 Perfect Matching

Def. A matching M ⊆ E is perfect if each node appears in exactly one

edge in M.

Q. When does a bipartite graph have a perfect matching?

Structure of bipartite graphs with perfect matchings.

■ Clearly we must have |L| = |R|.
■ What other conditions are necessary?
■ What conditions are sufficient?

9
 Perfect Matching

Notation. Let S be a subset of nodes, and let N(S) be the set of nodes
adjacent to nodes in S.

Observation. If a bipartite graph G = (L ∪ R, E), has a perfect

matching, then |N(S)| ≥ |S| for all subsets S ⊆ L.
Pf. Each node in S has to be matched to a different node in N(S).

1 1'

2 2' No perfect matching:

S = { 2, 4, 5 }
3 3' N(S) = { 2', 5' }.

4 4'

L 5 5' R
10
 Marriage Theorem

Marriage Theorem. [Frobenius 1917, Hall 1935] Let G = (L ∪ R, E) be a

bipartite graph with |L| = |R|. Then, G has a perfect matching iff |
N(S)| ≥ |S| for all subsets S ⊆ L.

Pf. ⇒ This was the previous observation.

1 1'

2 2' No perfect matching:

S = { 2, 4, 5 }
3 3' N(S) = { 2', 5' }.

4 4'

L 5 5' R
11
7.6 Disjoint Paths
 Edge Disjoint Paths

Disjoint path problem. Given a digraph G = (V, E) and two nodes s and t,
find the max number of edge-disjoint s-t paths.

Def. Two paths are edge-disjoint if they have no edge in common.

Ex: communication networks.

2 5

s 3 6 t

4 7

15
 Edge Disjoint Paths

Disjoint path problem. Given a digraph G = (V, E) and two nodes s and t,
find the max number of edge-disjoint s-t paths.

Def. Two paths are edge-disjoint if they have no edge in common.

Ex: communication networks.

2 5

s 3 6 t

4 7

16
 Edge Disjoint Paths

Max flow formulation: assign unit capacity to every edge.

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

Theorem. Max number edge-disjoint s-t paths equals max flow value.
Pf. ≤
■ Suppose there are k edge-disjoint paths P1, . . . , Pk.
■ Set f(e) = 1 if e participates in some path Pi ; else set f(e) = 0.
■ Since paths are edge-disjoint, f is a flow of value k. ▪

17
 Edge Disjoint Paths

Max flow formulation: assign unit capacity to every edge.

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

Theorem. Max number edge-disjoint s-t paths equals max flow value.
Pf. ≥
■ Suppose max flow value is k.
■ Integrality theorem ⇒ there exists 0-1 flow f of value k.
■ Consider edge (s, u) with f(s, u) = 1.
– by conservation, there exists an edge (u, v) with f(u, v) = 1
– continue until reach t, always choosing a new edge
■ Produces k (not necessarily simple) edge-disjoint paths. ▪
can eliminate cycles to get simple paths if desired
18
 Network Connectivity

Network connectivity. Given a digraph G = (V, E) and two nodes s and t,

find min number of edges whose removal disconnects t from s.

Def. A set of edges F ⊆ E disconnects t from s if all s-t paths uses at

least on edge in F.

2 5

s 3 6 t

4 7

19
 Edge Disjoint Paths and Network Connectivity

Theorem. [Menger 1927] The max number of edge-disjoint s-t paths is

equal to the min number of edges whose removal disconnects t from s.

Pf. ≤
■ Suppose the removal of F ⊆ E disconnects t from s, and |F| = k.
■ All s-t paths use at least one edge of F. Hence, the number of edge-
disjoint paths is at most k. ▪

2 5 2 5

s 3 6 t s 3 6 t

4 7 4 7
20
 Disjoint Paths and Network Connectivity

Theorem. [Menger 1927] The max number of edge-disjoint s-t paths is

equal to the min number of edges whose removal disconnects t from s.

Pf. ≥
■ Suppose max number of edge-disjoint paths is k.
■ Then max flow value is k.
■ Max-flow min-cut ⇒ cut (A, B) of capacity k.
■ Let F be set of edges going from A to B.
■ |F| = k and disconnects t from s. ▪

2 5 2 5
A

s 3 6 t s 3 6 t

4 7 4 7
21
7.7 Extensions to Max Flow
 Circulation with Demands

Circulation with demands.

■ Directed graph G = (V, E).
■ Edge capacities c(e), e ∈ E.
■ Node supply and demands d(v), v ∈ V.

demand if d(v) > 0; supply if d(v) < 0; transshipment if d(v) = 0

Def. A circulation is a function that satisfies:

■For each e ∈ E: 0 ≤ f(e) ≤ c(e) (capacity)
■For each v ∈ V: ∑ f (e) − ∑ f (e) = d (v) (conservation)
e in to v e out of v

Circulation problem: given (V, E, c, d), does there exist a circulation?

€

23
 Circulation with Demands

Necessary condition: sum of supplies = sum of demands.

∑ d (v) = ∑ − d (v) =: D
v : d (v) > 0 v : d (v) < 0

Pf. Sum conservation constraints for every demand node v.

-8 -6 supply

6 1
4 7 7 7
10 6 6 9
4 2
-7
3
3 4 11
10 0 4
capacity demand
flow

24
 Circulation with Demands

Max flow formulation.

-8 -6 supply
G:
4 7 7
10 6 9
4
-7

3 4 11
10 0
demand

25
 Circulation with Demands

Max flow formulation.

■Add new source s and sink t.
■For each v with d(v) < 0, add edge (s, v) with capacity -d(v).
■For each v with d(v) > 0, add edge (v, t) with capacity d(v).
■Claim: G has circulation iff G' has max flow of value D.
saturates all edges
leaving s and entering t
s

7 8 6 supply
G':
7 7
10 6 9
4

3 4
0
10 11 demand

26
 Circulation with Demands

Integrality theorem. If all capacities and demands are integers, and

there exists a circulation, then there exists one that is integer-valued.

Pf. Follows from max flow formulation and integrality theorem for max
flow.

Characterization. Given (V, E, c, d), there does not exists a circulation

iff there exists a node partition (A, B) such that Σv∈B dv > cap(A, B)

Pf idea. Look at min cut in G'. demand by nodes in B exceeds supply

of nodes in B plus max capacity of
edges going from A to B

27
7.10 Image Segmentation
 Image Segmentation

Image segmentation.
■Central problem in image processing.
■Divide image into coherent regions.

Ex: Three people standing in front of complex background scene.

Identify each person as a coherent object.

34
 Image Segmentation

Foreground / background segmentation.

■ Label each pixel in picture as belonging to
foreground or background.
■ V = set of pixels, E = pairs of neighboring pixels.
■ ai ≥ 0 is likelihood pixel i in foreground.
■ bi ≥ 0 is likelihood pixel i in background.
■ pij ≥ 0 is separation penalty for labeling one of i
and j as foreground, and the other as background.

Goals.
■ Accuracy: if ai > bi in isolation, prefer to label i in foreground.
■ Smoothness: if many neighbors of i are labeled foreground, we
should be inclined to label i as foreground.
■ Find partition (A, B) that maximizes: ∑ a i + ∑ b j − ∑ pij
i∈ A j∈B (i, j) ∈ E
foreground background A{i, j} = 1

35
€
 Graph Cut

J. Kosecka
Interactive Foreground Segmentation

Interaction Foreground Segmentation: Grab Cuts

Rother, Kolmogorov, Blake, SIGRAPH 2005
 Image Segmentation

Formulate as min cut problem.

■ Maximization.
■ No source or sink.
■ Undirected graph.

Turn into minimization problem.

■ Maximizing ∑ a i + ∑bj − ∑ pij

i∈ A j∈B (i, j) ∈ E
A{i, j} = 1

is equivalent to minimizing (∑

i ∈ V ai + ∑ j ∈ V b j) − ∑ a i − ∑ bj + ∑ pij
€  i∈ A j∈B (i, j) ∈ E
a constant A{i, j} = 1

■ or alternatively ∑ a j + ∑ bi + ∑ pij
j∈B i∈ A (i, j) ∈ E
€ A{i, j} = 1

38
€
 Image Segmentation

Formulate as min cut problem. pij

■ G' = (V', E').
pij
Add source to correspond to foreground;
pij
■

add sink to correspond to background

■ Use two anti-parallel edges instead of
undirected edge.

aj

i pij j
s t

bi

G'
39
 Image Segmentation

Consider min cut (A, B) in G'.

■ A = foreground.
cap(A, B) = ∑ a j + ∑ bi + ∑ pij if i and j on different sides,
j∈B i∈ A (i, j) ∈ E pij counted exactly once
i∈ A, j ∈ B

■ Precisely the quantity we want to minimize.

€

aj

i pij j
s t

bi
A

G'
40
 Graph Cut

Formulated as maximum cost flow - Network flow problem from Graph Theory
Kolmogorov, Boykov (et al)
 Ex.:Foreground/Background Segmentation

• Two categories: regions of interest/background

• Segmentation of CT scans into organs (lungs, heart etc)
• Binary segmentation (regions and background)

Y. Boykov and G. Funka-Lea, Graph-Cuts and Efficient

N-D Segmentation, IJCV 06
Ex: Interactive Foreground Segmentation

Interaction Foreground Segmentation: Grab Cuts

Rother, Kolmogorov, Blake, SIGRAPH 2005
7.11 Project Selection
 Project Selection

can be positive or negative

Projects with prerequisites.
■ Set P of possible projects. Project v has associated revenue pv.
– some projects generate money: create interactive e-commerce interface,
redesign web page
– others cost money: upgrade computers, get site license
■ Set of prerequisites E. If (v, w) ∈ E, can't do project v and unless
also do project w.
■ A subset of projects A ⊆ P is feasible if the prerequisite of every
project in A also belongs to A.

Project selection. Choose a feasible subset of projects to maximize

revenue. General framework for modeling similar decisions.

45
 Project Selection: Prerequisite Graph

Prerequisite graph.
■ Include an edge from v to w if can't do v without also doing w.
■ {v, w, x} is feasible subset of projects.
■ {v, x} is infeasible subset of projects.
■ Select a set of projects A such that every project in A has also
prerequisite in A
w w

v x v x

feasible infeasible

46
 Project Selection: Min Cut Formulation

Min cut formulation.

■ Assign capacity ∞ to all prerequisite edge.
■ Add edge (s, v) with capacity -pv if pv > 0.
■ Add edge (v, t) with capacity -pv if pv < 0.
■ For notational convenience, define ps = pt = 0.

u ∞ w
∞
pu ∞ -pw

s py y ∞ z -pz t

pv ∞ -px
v ∞ x

∞
47
 Project Selection: Min Cut Formulation

Claim. (A, B) is min cut iff A - { s } is optimal set of projects.

■ Infinite capacity edges ensure A - { s } is feasible.
■ Max revenue because: cap(A, B) = ∑ p v + ∑ (− p v )
v∈ B: pv > 0 v∈ A: pv < 0
= ∑pv − ∑pv
■ Max revenue, capacity of the cut v: pv > 0
 v ∈ A
constant

€ w u

A pu
-pw
s py y z t

pv ∞ -px
v ∞ x

∞
48
 7.12 Baseball Elimination

"See that thing in the paper last week about Einstein? . . .

Some reporter asked him to figure out the mathematics of
the pennant race. You know, one team wins so many of their
remaining games, the other teams win this number or that
number. What are the myriad possibilities? Who's got the
edge?"
"The hell does he know?"
"Apparently not much. He picked the Dodgers
to eliminate the Giants last Friday."

- Don DeLillo, Underworld

 Baseball Elimination

Team Wins Losses To play Against = rij

i wi li ri Atl Phi NY Mon
Atlanta 83 71 8 - 1 6 1
Philly 80 79 3 1 - 0 2
New York 78 78 6 6 0 - 0
Montreal 77 82 3 1 2 0 -

Which teams have a chance of finishing the season with most wins?
■Montreal eliminated since it can finish with at most 80 wins, but
Atlanta already has 83.
■wi + ri < wj ⇒ team i eliminated.
■Only reason sports writers appear to be aware of.
■Sufficient, but not necessary!

51
 Baseball Elimination

Team Wins Losses To play Against = rij

i wi li ri Atl Phi NY Mon
Atlanta 83 71 8 - 1 6 1
Philly 80 79 3 1 - 0 2
New York 78 78 6 6 0 - 0
Montreal 77 82 3 1 2 0 -

Which teams have a chance of finishing the season with most wins?
■Philly can win 83, but still eliminated . . .
■If Atlanta loses a game, then some other team wins one.

Remark. Answer depends not just on how many games already won and
left to play, but also on whom they're against.

52
 Baseball Elimination

Baseball elimination problem.

■ Set of teams S.
■ Distinguished team s ∈ S.
■ Team x has won wx games already.
■ Teams x and y play each other rxy additional times.
■ Is there any outcome of the remaining games in which team s
finishes with the most (or tied for the most) wins?

54
 Baseball Elimination: Max Flow Formulation

Can team 3 finish with most wins?

■ Assume team 3 wins all remaining games ⇒ w3 + r3 wins.
■ Divvy remaining games so that all teams have ≤ w3 + r3 wins.

1-2
1

team 4 can still

1-4 win this many
games left 2 more games

∞
1-5

s r24 = 7 2-4 ∞ 4 w3 + r3 - w4 t

2-5

game nodes 4-5 team nodes

55
 Baseball Elimination: Max Flow Formulation

Theorem. Team 3 is not eliminated iff max flow saturates all edges
leaving source.
■ Integrality theorem ⇒ each remaining game between x and y added
to number of wins for team x or team y.
■ Capacity on (x, t) edges ensure no team wins too many games.

1-2
1

team 4 can still

1-4 win this many
games left 2 more games

∞
1-5

s r24 = 7 2-4 ∞ 4 w3 + r3 - w4 t

2-5

game nodes 4-5 team nodes

56
 Baseball Elimination: Explanation for Sports Writers

Team Wins Losses To play Against = rij

i wi li ri NY Bal Bos Tor Det
NY 75 59 28 - 3 8 7 3
Baltimore 71 63 28 3 - 2 7 4
Boston 69 66 27 8 2 - 0 0
Toronto 63 72 27 7 7 0 - -
Detroit 49 86 27 3 4 0 0 -
AL East: August 30, 1996

Which teams have a chance of finishing the season with most wins?
■Detroit could finish season with 49 + 27 = 76 wins.

57
 Baseball Elimination: Explanation for Sports Writers

Team Wins Losses To play Against = rij

i wi li ri NY Bal Bos Tor Det
NY 75 59 28 - 3 8 7 3
Baltimore 71 63 28 3 - 2 7 4
Boston 69 66 27 8 2 - 0 0
Toronto 63 72 27 7 7 0 - -
Detroit 49 86 27 3 4 0 0 -
AL East: August 30, 1996

Which teams have a chance of finishing the season with most wins?
■Detroit could finish season with 49 + 27 = 76 wins.

Certificate of elimination. R = {NY, Bal, Bos, Tor}

■ Have already won w(R) = 278 games.
■ Must win at least r(R) = 27 more.
■ Average team in R wins at least 305/4 > 76 games.
58
 Baseball Elimination: Explanation for Sports Writers

Certificate of elimination.
# remaining games
# 
wins   
T ⊆ S, w(T ) := ∑ wi , g(T ) := ∑ gx y ,
i∈T {x, y} ⊆ T

LB on avg # games won

 
€ w(T ) + g(T )
If > wz + g z then z is eliminated (by subset T).
|T |

Theorem. [Hoffman-Rivlin 1967] Team z is eliminated iff there exists

€
a subset T* that eliminates z.

Proof idea. Let T* = team nodes on source side of min cut.

59
 Baseball Elimination: Explanation for Sports Writers

Pf of theorem.
■ Use max flow formulation, and consider min cut (A, B).
■ Define T* = team nodes on source side of min cut.
■ Observe x-y ∈ A iff both x ∈ T* and y ∈ T*.
– infinite capacity edges ensure if x-y ∈ A then x ∈ A and y ∈ A
– if x ∈ A and y ∈ A but x-y ∈ T, then adding x-y to A decreases
capacity of cut

team x can still win this

many more games
games left
y

∞
s r24 = 7 x-y ∞ x wz + rz - wx t

60
 Baseball Elimination: Explanation for Sports Writers

Pf of theorem.
■ Use max flow formulation, and consider min cut (A, B).
■ Define T* = team nodes on source side of min cut.
■ Observe x-y ∈ A iff both x ∈ T* and y ∈ T*.
■ g(S − {z}) > cap(A, B)
capacity of game edges leaving s capacity of team edges leaving s
    
= g(S − {z}) − g(T *) + ∑ (wz + gz − wx )
x ∈ T*
= g(S − {z}) − g(T *) − w(T *) + | T * | (wz + gz )

€ w(T *) + g(T *)
■ Rearranging terms: wz + gz < ▪
|T*|

61