Max-flow and min-cut

Max-Flow and Min-Cut

Two important algorithmic problems, which yield a beautiful

duality
Myriad of non-trivial applications, it plays an important role in the
optimization of many problems:
Network connectivity, airline schedule (extended to all means of
transportation), image segmentation, bipartite matching,
distributed computing, data mining, · · · · · ·
Flow Networks
Network diagraph G = (V , E ) s.t. it has
2 a 1
I source vertex s ∈ V
I sink vertex t ∈ V s 2 1 t
I edge capacities c : E → R+ ∪ {0} 1 2
b
Flow f : V × V → R+ ∪ {0} s.t.
Kirchoff’s laws:
I ∀(u, v ) ∈ E , 0 ≤ f (u, v ) ≤ c(u, v ),
(Flow P ∀v ∈ V − {s, t},
conservation)
I
2/ 2 a 1/ 1
P
u∈V f (u, v ) = z∈V f (v , z) s 1/ 2 1 t
I The value of a flow
1/ 1 2/ 2
X b
|f | = f (s, v ) = f (s, V ) = f (V , t). Value |f|=3
v ∈V
The Maximum flow problem

INPUT: Given a flow network (G = (V , E ), s, t, c)

QUESTION: Find a flow of maximum value on G .

2/2
A D
2/2
2/4 0/9 1/1
1/5
S B 0/3 T
1/2
4/4 5/5
C E
5/5

The value of the max-flow is 7 = 4 + 1 + 2 = 5 + 2.

Notice: Although the flow exiting s is not maximum, the flow
going into t is maximum (= max. capacity).
Therefore the total flow is maximum.
The s − t cut
Given (G = (V , E ), s, t, c) a s − t cut is a partition of V = S ∪ T
so S ∩ T = ∅), with s ∈ S and t ∈ T .
The flowPacross
Pthe cut: P P
f (S) = u∈S v ∈T f (u, v ) − v ∈S u∈T f (v , u).
P P
The capacity of the cut: c(S) = u∈S v ∈T f (u, v )
capacity of cut (S, T ) = sum of weights leaving S.
Notice because of the capacity constrain: f (S) ≤ c(S)

2/2 S = {s,c,d}
a d
2/2 T={a,b,e,t}
2/4 0/9 1/1
1/5
s b 0/3 t
1/2 c(S,T)=(4+5+5)+(3+2)=19
4/4 5/5
c e f(S,T)=(2+1+5)+(0+2−1−2)=7
5/5
The s − t cut
Given (G = (V , E ), s, t, c) a s − t cut is a partition of V = S ∪ T
so S ∩ T = ∅), with s ∈ S and t ∈ T .
The flowPacross
Pthe cut: P P
f (S) = u∈S v ∈T f (u, v ) − v ∈S u∈T f (v , u).
P P
The capacity of the cut: c(S) = u∈S v ∈T f (u, v )
Notice because of the capacity constrain: f (S) ≤ c(S)

2/2 S = {s,c,a}
a d
2/2 T={d,b,e,t}
2/4 0/9 1/1
1/5
s b 0/3 t
1/2 c(S,T)=2+5+5=12
4/4 5/5
c e f(S,T)=2+1+5−1=7
5/5
Notation
Given v ∈ G and cut (S, T ) and a v ∈ S, let S 0 = S − {v }. Then
I Denote f (S 0 , T ) flow between S 0 and T (without passing by
v ), i.e.
f (S 0 , T ) = u∈S 0 w ∈T f (u, w ) − w ∈T u∈S 0 f (w , u)
P P P P
with (u, w ) ∈ E and (u, w ) ∈ E ,
P
I denote f (v , T ) flow v → T i.e. f (v , T ) = u∈T f (v , u),
P
I denote f (T , v ) flow T → v i.e. f (T , v ) = u∈T f (u, v ),
denote f (S 0 , v ) flow S 0 → v i.e. f (S 0 , v ) = u∈S 0 f (u, v ),
P
I

denote f (v , S 0 ) flow v → S 0 i.e. f (v , S 0 ) = u∈S 0 f (v , u),

P
I

T
s S’ t

S v
Any s − t cut has the same flow
Theorem
Given (G , s, t, c) the flow through any s − t cut (S, T ) is
f (S) = |f |.
Proof (Induction on |S|)
I If S = {s} then f (S) = |f |.
I Assume it is true for S 0 = S − {v }, i.e. f (S 0 ) = |f |.
Notice f (S 0 ) = f (S 0 , T ) + f (S 0 , v ) − f (v , S 0 ). Moreover from
the flow conservation, f (S 0 , v ) + f (T , v ) = f (v , S 0 ) + f (v , T )
⇒ f (v , T ) − f (T , v ) = f (S 0 , v ) − f (v , S 0 )
| {z }
∗
I Then f (S) = f (S 0 , T ) + f (v , T ) − f (T , v ), using (∗)
f (S) = f (S 0 ) = |f | 2

T
s S’ t

S v
Residual network
Given a network (G = (V , E ), s, t, c) together with a flow f on it,
the residual network, (Gf = (V , Ef ), cf ) is the network with the
same vertex set and edge set:
I if c(u, v ) − f (u, v ) > 0 then (u, v ) ∈ Ef and
cf (u, v ) = c(u, v ) − f (u, v ) > 0 (forward edges), and
I if f (u, v ) > 0 then (v , u) ∈ Ef and cf (v , u) = f (u, v )
(backward edges). i.e. there are f (u, v ) units of flow we can
undo, by pushing flow backward
I the cf are denoted residual capacity.

2/2 a 0/1 a 1
2
s 2/3 t s 2 1 t
Gf
0/1 b 2/2 1 b 2
Residual network: Augmenting paths

Given G = (V , E ) and a flow f on G , an augmenting path P is

any simple path in Gf (using forward and backward edges, but
P:s t).
Given f : s t in G and P in Gf define the bottleneck (P, f ) to be
the minimum residual capacity of any edge in P, with respect to f .

a 1 a 1/1 a 1
2 2/2 2

Gf s 2 1 t s 1/3 t s 1 2 t
1 2 1/1 2/2 G f´ 1 2
b f´ b b
P: dotted line
Residual network: Augmenting paths

Given G = (V , E ) and a flow f on G , an augmenting path P is

any simple path in Gf .
Given f s → t in G and P in Gf define the bottleneck (P, f ) to be
the minimum residual capacity of any edge in P.
Augment(P, f )
b=bottleneck (P, f )
for each (u, v ) ∈ P do
if (u, v ) is forward edge in G then 2/2 a 1/1
Increase f (u, v ) in G by b
else s 1/3 t
Decrease f (u, v ) in G by b f’
end if 1/1 b 2/2
end for
return f
Residual network: Augmenting paths

Lemma
Consider f 0 =Augment(P, f ), then f 0 is a flow in G .
Proof: We have to prove that (1) ∀e ∈ E , 0 ≤ f (e) ≤ c(e) and
that ∀v flow to v = flow out of v .
I Capacity law Forward edges (u, v ) ∈ P we increase f (u, v ) by
b, as b ≤ c(u, v ) − f (u, v ) then
f 0 (u, v ) = f (u, v ) + b ≤ c(u, v ).
Backward edges (u, v ) ∈ P we decrease f (v , u) by b, as
b ≤ f (v , u), f 0 (v , u) = f (u, v ) − b ≥ 0.
I Conservation law, ∀v ∈ P given edges e1 , e2 in P and incident
to v , it is easy to check the 4 cases based whether e1 , e2 are
forward or backward edges. 2
Max-Flow Min-Cut theorem
Theorem
For any (G , s, t, c) the value of the max flow f ∗ is equal to the
capacity of the min s − t-cut (over all s − t cuts in G )
This is typical example of LP duality!
Proof:
I For any s − t cut (S, T ) in G ⇒ f (S) ≤ c(S, T ).
I Suppose by hypothesis that f ∗ in G is a max flow, i.e. f ∗ has
no augmenting path, then Gf ∗ has no s ; t path. Let
Ss = {v ∈ V |∃s ; v in Gf ∗ }, notice t 6∈ Ss and moreover
(Ss , V − {Ss }) is a s − t cut in Gf ∗ ⇒ ∀v ∈ Ss , u ∈ V − {Ss }
we have not residual edges in the cut, so that in G
f ∗ (v , u) = c(v , u), and therefore
c(Ss , V − {Ss }) = f ∗ (Ss , V − {Ss }) in G .
I As any max-flow must be ≤ min-cut, then in particular
(Ss , V − {Ss }) is a min-cut in G and it is equal to the
max-flow f ∗ . 2
Ford-Fulkerson algorithm
L.R. Ford, D.R. Fulkerson:
Maximal flow through a
network. Canadian J. of Math.
1956.

Ford-Fulkerson(G , s, t, c) 0/10 a 0/30

for all (u, v ) ∈ E let f (u, v ) = 0
Gf = G G s 0/10 t f=0
while there is an s − t path in Gf do 0/20 0/15
find a simple path P in Gf (use DFS) b
f 0 = Augment(f , P)
Update f to f 0
Update Gf to Gf 0 a
10 30
end while Gf P
s 10 t
return f
20 15
b
Ford-Fulkerson algorithm
L.R. Ford, D.R. Fulkerson:
Maximal flow through a
network. Canadian J. of Math.
1956.

Ford-Fulkerson(G , s, t, c) 10/10 a 10/30

for all (u, v ) ∈ E let f (u, v ) = 0
Gf = G G s 0/10 t f=10
while there is an s − t path in Gf do 0/20 0/15
find a simple path P in Gf (use DFS) b
f 0 = Augment(f , P)
Update f to f 0
Update Gf to Gf 0 a 20
10
end while Gf P
s 10 10 t
return f
20 b 15
Ford-Fulkerson algorithm
L.R. Ford, D.R. Fulkerson:
Maximal flow through a
network. Canadian J. of Math.
1956.

Ford-Fulkerson(G , s, t, c) 10/10 a 10/30

for all (u, v ) ∈ E let f (u, v ) = 0
Gf = G G s 0/10 t f=25
while there is an s − t path in Gf do 15/20 15/15
find a simple path P in Gf (use DFS) b
f 0 = Augment(f , P)
Update f to f 0
a 20
Update Gf to Gf 0 10
end while Gf s 5 10 10 P
t
return f
b 15
15
Ford-Fulkerson algorithm
L.R. Ford, D.R. Fulkerson:
Maximal flow through a
network. Canadian J. of Math.
1956.

Ford-Fulkerson(G , s, t, c) 10/10 a 15/30

for all (u, v ) ∈ E let f (u, v ) = 0
Gf = G G s 10/10 t f=30
while there is an s − t path in Gf do 20/20 15/15
find a simple path P in Gf (use DFS) b
f 0 = Augment(f , P)
Update f to f 0
a 15
Update Gf to Gf 0 10
end while Gf s 5 10 15 No P
t
return f
b 15
15
Analysis of Ford Fulkerson

We are considering networks that initial flow and capacities are

integers,
Lemma (Integrality invariant)
At every iteration of the Ford-Fulkerson algorithm, the flow values
f (e) and the residual capacities in Gf are integers.
Proof: (induction)
I The statement is true before the while loop.
I Inductive Hypothesis: The statement is true after j iterations.
I iteration j + 1: As all residual capacities in Gf are integers,
then bottleneck (P, f ) ∈ Z, for the augmenting path found in
iteration j + 1. Thus the flow f 0 will have integer values ⇒ so
will the capacities in the new residual graph. 2
Integrality theorem

Theorem (Integrality theorem)

There exists a max-flow f ∗ for which every flow value f ∗ is an
integer.
Proof:
Since the algorithm terminates, the theorem follows from the
integrality invariant lemma. 2
Notice the integrality theorem doesn’t say that every max-flow is
integer valued, it only says at least one max-flow has the property
of being integer valued.
Analysis of Ford Fulkerson

Lemma
If f is a flow in G and f 0 is the flow after an augmentation, then
|f | < |f 0 |.
Proof: Let P be the augmenting path in Gf . The first edge e ∈ P
leaves s, and as G has no incoming edges to s, e is a forward edge.
Moreover P is simple ⇒ never returns to s. Therefore, the value of
the flow increases in edge e. 2
Correctness of Ford-Fulkerson

Consequence of the Max-flow min-cut theorem.

Theorem
The flow returned by Ford-Fulkerson f ∗ is the max-flow.
Proof:
I For any flow f and s − t cut (S, T ) we have |f | ≤ c(S, T ).
I The flow f ∗ is such that |f ∗ | = c(S ∗ , T ∗ ), for some s − t cut
(S ∗ , T ∗ ) ⇒ f ∗ is the max-flow. 2

Therefore, for any (G , s, t, c) the value of the max s − t flow is

equal to the capacity of the minimum s − t cut.
Analysis of Ford Fulkerson: Running time

Lemma
Let C be the minimum cut value, Ford-Fulkerson terminates after
finding at most C augmenting paths.
Proof: The value of the flow increases by ≥ 1 after each
augmentation. 2

I The number of iterations is ≤ C . At each iteration:

I We have to modify Gf , with E (Gf ) ≤ 2m, to time O(m).
I Using DFS, the time to find an augmenting path P is
O(n + m)
I Total running time is O(C (n + m)) = O(Cm)
I Is that polynomic?
Running time of Ford-Fulkerson

The number of iterations of 2/C a 1/C

Ford-Fulkerson could be Ω(C ) s 1/1 1/1 t
As it is described Ford-Fulkerson can 2/C 1/C
b
alternate C times between the blue
C=1000000000
and red paths if the figure. 2000 million iteractions
in a G with 4 vertices!!

Recall a pseudopolynomial algorithm is an algorithm that is

polynomial in the unary encoding of the input.
So the complexity of Ford-Fulkerson algorithm is equivalent to the
PD Algorithm for 0-1 Knapsack.
Is there a polynomial time algorithm for the max-flow problem?
Edmonds-Karp, Dinic algorithm

J.Edmonds, R. Karp: Theoretical improvements in algorithmic

efficiency for network flow problems. Journal ACM 1972.
Y. Dinic: Algorithm for solution of a problem of maximum flow in
a network with power estimation. Doklady Ak.N. 1970
Choosing a good
augmenting path can lead
to a faster algorithm.
Use BFS to find shorter
augmenting paths in Gf .

Using BFS on Gf we can find the shortest augmenting path P in

O(m), independently of max capacity C .
Edmonds-Karp algorithm

Uses BFS to find the augmenting path at each Gf with fewer

number of edges.

Edmonds-Karp(G , s, t, c)
For all e = (u, v ) ∈ E let f (u, v ) = 0
G0 = G a
C C
while there is an s t path in Gf
s 1 1 t
do
P = BFS(Gf , s, t) C b C
f 0 = Augment(f , P)
Update Gf = Gf 0 and f = f 0 The BFS in EK will
choose: or
end while
return f
Level graph
Given G = (V , E ), s, define LG = (V , EG ) to be its the level graph
by:
I `(v ) = number of edges in shortest path s v in G ,
I LG = (V , EG ) is the subgraph of G that contains only edges
(v , w ) ∈ E s.t. `(w ) = `(v ) + 1.
Notice:
I Using BFS we can compute LG in O(n + m)
I Important property: P is a shortest s ; t in G iff P is an
s ; t path in LG .

a 2 d a 2 d
2 2
4 1 4 1
9
s 5 b 3 t s 5 b t
2
4 5 4 5
G LG
c e c e
5 5
1 2 3 1 2 3
The working of the EK algorithm
G,f G,f´
a 2 d a 2 d
2 1/2
4 9 1 4 9 1/1
s 5 b 3 t s 1/5 b 3 t
2
2
4/4 4/4
4/5 4/5
c e c e
4/5 4/5
a 2 d a 2 d 1
2 1
4 1 4 9 1
9
s 5 b 3 4 t s 4 b 2 3 4 t
2
4 1 4
1 1
Gf 4 G f’ 4
c e c e
1 1

a 2 d a 1/2 d
1/2 1/1
4 1/1 1/4
s
1/5 b 3 t 4
2 s b
2 3 t

L 1 L 1
c e c e
The working of the EK algorithm

a 1/2 d 1 a 1 1 d 1
1/1
1/4 1 3 9 1
s b 3 t s 4 b 2 3 4 t
2 1 4
1 1
G f’’ 4
c e c e
1
a 1/2 d a 1 d
1/4 1/1 2/2 1
9
1/5 s 4 b 1 t
s b 2 3 t 2

4/5 1
4/4 L f’’
c e c e
4/5 1
G,f’’
a 2/2 d
2/4 1/1 2/2
9
1/5
s b 2 1/3 t

4/4 5/5
G,f*
c e
4/5
EK algorithm: Properties
Lemma
Throughout the algorithm, the length of the shortest path never
decreases.
Proof:
I Let f and f 0 be the flow before and after a shortest path
augmentation
I let L and L0 be the levels graphs of Gf and Gf 0 .
I Only back edges added to Gf 0 . 2

Lemma
After at most m shortest path augmentations, the length of P is
monotonically increasing.
Proof:
I The bottleneck edge is deleted from L after each
augmentation.
I No new edge is added to L until length of shortest path
strictly increases 2
Complexity of Edmonds-Karp algorithm

Using the the previous lemmas, we prove

Theorem
The EK algorithms runs in O(m2 n) steps. Therefore it is a
polynomial time algorithm.
Proof:
I Need time O(m + n) to find the augmenting path using BFS.
I Need O(m) augmentations for paths of length k.
I Every augmentation path is simple ⇒ 1 ≤ k ≤ n ⇒ O(nm)
augmentations 2
Finding a min-cut
Given (G , s, t, c) to find a min-cut:
1. Compute the max-flow f ∗ in G .
2. Obtain Gf ∗ .
3. Find the set S = {v ∈ V |s ; v } in Gf ∗ .
4. Output the cut
(S, V − {S}) = {(v , u)|v ∈ Sandu ∈ V − {S}} in G .

The running time is the same than the algorithm to find the
max-flow.

2/2
a d 2 a 2 d
2/2
2/4 0/9 1/1 2 9 1 2
1/5 4
s b 0/3 t s b 3 t
1/2 1
4/4 S 1
5/5 4 1 5
c e c e
5/5 5
The max-flow problems: History

I Ford-Fulkerson (1956) O(mC ), where C is max capacity.

I Dinic (1970) (blocking flow) O(n2 m)
I Edmond-Karp (1972) (shortest augmenting path) O(nm2 )
I Karzanov (1974), O(n2 m) Goldberg-Tarjant (1986) (push
re-label preflow + dynamic trees) O(nm lg(n2 /m)) (for this
time uit uses parallel implementation)
I King-Rao-Tarjan (1998) O(nm logm/n lg n n).
I J. Orlin (2013) O(nm) (clever follow up to KRT-98)
Maximum matching problem

Given an undirected graph G = (V , E ) a subset of edges M ⊆ E is

a matching if each node appears at most in one edge (a node may
not appear at all).
A perfect matching in G is a matching M such that |M| = |V |/2
The maximum matching problem given a graph G a matching with
maximum cardinality.
Maximum matching in graphs bipartite
A graph G = (V , E ) is said to be bipartite if V can be partite in L
and R, L ∪ R = V , L ∩ R = ∅, such that every e ∈ E connects L
with R.

The max matching bipartite graph problem: given a bipartite

G = (L ∪ R, E ) with 2n vertices find a maximum matching.

Max matchings = 4
Maximum matching: flow formulation

Given a bipartite graph G = (L ∪ R, E ) construct Ĝ = (V̂ , Ê ):

I Add vertices s and t: V̂ = L ∪ R ∪ {s, t}.
I Add directed edges s → L with capacity 1. Add directed
edges R → t with capacity 1.
I Direct the edges E from L to R, and give them capacity ∞.
I Ê = {s → L} ∪ E ∪ {R → t}.

1 1

s t

1 1
Maximum matching: flow formulation

Given a bipartite graph G = (L ∪ R, E ) construct Ĝ = (V̂ , Ê ):

I Add vertices s and t: V̂ = L ∪ R ∪ {s, t}.
I Add directed edges s → L with capacity 1. Add directed
edges R → t with capacity 1.
I Direct the edges E from L to R, and give them capacity ∞.
I Ê = {s → L} ∪ E ∪ {R → t}.

1 1

s t

1 1
Maximum matching: Analysis

Theorem
Max flow in Ĝ =Max bipartite matching in G .
Proof ≤
Given a matching M in G with k-edges,
consider the flow F that sends 1 unit along each one of the k
paths.
f is a flow and has value k.
0
1 1 1
1
1 1
1
s t
1
1 1 1
0 1
1
1 11
Maximum matching: Analysis
Max flow ≤Max bipartite matching
I If there is a flow f in Ĝ , |f | = k, as capacities are Z∗ ⇒ an
integral flow existsis.
I Consider the cut C = ({s} ∪ L, R ∪ {t}) in Ĝ .
I Let F be the set of edges in C with flow=1, then |F | = k.
I Each node in L is in at most one e ∈ F and every node in R is
in at most one head of an e ∈ F
I Therefore, exists a bipartite matching F in G with |F | ≤ |f | 2
0
1 1 1
1
1 1
1
s t
1
1 1 1
1 0
1 11 1
Disjoint path problem

Given a digraph (G = (V , E ), s, t), a set of paths is edge-disjoint if

their edges are disjoint (although them may go through some of
the same vertices)
The disjoint path problem given G , s, t find the max number of
edge disjoint paths s ; t

c
e d
s t

a b
Disjoint path problem

Given a digraph (G = (V , E ), s, t), a set of paths is edge-disjoint if

their edges are disjoint (although them may go through some of
the same vertices)
The disjoint path problem given G , s, t find the max number of
edge disjoint paths s ; t

c
e d
s t

a b
Disjoint path problem: Max flow formulation

Assign unit capacity to every edge

Theorem
The max number of edge disjoint paths s ; t is equal to the max
flow value
1 c 1 1 c 1
1 1 1 1
1 e 1 d 1 e d
1 t 1 t
s s
1 1
1 1 1 1 1 1
a b a b
Max flow=3 1
1
Disjoint path problem: Proof of the Theorem

Number of disjoints paths ≤ max flow

If we have k edge-disjoints paths s ; t in G then making f (e) = 1
for each e in a path, we get a flow = k
Number of disjoints paths ≥ max flow
If max flow |f ∗ | = k ⇒ ∃ 0-1 flow f ∗ with value k
⇒ ∃k edges (s, v ) s.t. f (s, v ) = 1, by flow conservation we can
extend to k paths s ; t, where each edge is a path carries flow
= 1. 2

If we have an undirected graph, with two distinguised nodes u, v ,

how would you apply the max flow formulation to solve the problem
of finding the max number of disjoint paths between u and t?
Circulation with demands

Given a graph G = (V , E ) with capacities c in the edges, such

that each v ∈ V is associate with a demand d(v ), where
I If d(v ) > 0 ⇒ v is a sink, v can
receive d(v ) units of flow more
than it sends. −3
I If d(v ) < 0 ⇒ v is a source, v can 3 3
send d(v ) units of flow more than 2
−3 2
it receives.
I If d(v ) = 0 then v is neither a 2 2

source or a sink. 4

I Let S be the set of sources and T

the set of sinks.
Circulation with demands problem

Given G = (V , E ) with c ≥ 0 and {d(v )}v ∈V , define a circulation

as a function f : E → R+ s.t.
1. capacity: For each −3
e ∈ E , 0 ≤ f (e) ≤ c(e), 1/ 3 2/ 3
2. conservation: For each v ∈ V , −3 2/2 2
X X
f (u, v )− f (v , z) = d(v ). 2/2 2/ 2
(u,v )∈E (v ,z)∈E 4

Circulation with demands feasibility problem: Given G = (V , E )

with c ≥ 0 and {d(v )}v ∈V , does it exists a feasible circulation?
Feasible circulation: a function f on G with c ≥ 0 and {d(v )}v ∈V ,
such that it satisfies (1) and (2)?
Circulation with demands problem
Notice that if f is a feasible circulation, then
 
 
X X X X 
d(v ) = f (u, v ) − f (v , z) .
 

 
v ∈V v ∈V (u,v )∈E (v ,z)∈E 
| {z } | {z }
edges to v edges out of v
P
For each e ∈ E we are counting twice f (e), then v ∈V d(v ) = 0.
And we have,
P If there is a feasible circulation with demands {d(v )}v ∈V , then
So
v ∈V d(v ) = 0.

Therefore as S = {v ∈ V |d(v ) > 0} 1/ 3

−3
2/ 3
and TP= {v ∈ V |d(v
P) < 0}, then −3 2/2 2
D = v ∈S d(v ) = v ∈T d(v ). 2/2 2/ 2
4
Circulation with demands: Max-flow formulation
Extend G = (V , E ) to G 0 = (V 0 , E 0 ) by
I Add new source s and sink s.
I For each v ∈ S (d(v ) < 0) add (s, v ) with capacity −d(v ).
I For each v ∈ T (d(v ) > 0) add (v , s) with capacity d(v ).

−3 3 −3
s
3 3 3 3
G G’ 3
−3 2 2 −3 2 2
S 2
2 2 2 2
4 4 t
T 4
Analysis

1.- Every flow f : s ; t in G 0 must be |f | ≤ D

The capacity c({s}, V ) = D ⇒ by max-flow min-cut Thm. any
max-flow f in G 0 , |f | ≤ D.
2.- If there is a feasible circulation f with {d(v )}v ∈V in G , then we
have a max-flow f : s ; t in G with |f | = D
∀(s, v ) ∈ E 0 , f 0 (s, v ) = −d(v ) and ∀(u, t) ∈ E 0 , f 0 (u, t) = d(v ).

−3
3/ 3 −3
s
1/ 3 2/ 3 1/ 3 2/ 3
G 2/2 G’ 3/ 3 2/ 2
−3 2 −3 2
2/ 2
2/2 2/ 2 2/ 2 2/ 2
4 4 t
4/ 4
Analysis

3.- If there is a flow f 0 : s ; t in G 0 with |f | = D:

1. ∀(s, v ) ∈ E 0 and ∀(u, t) ∈ E 0 must be saturated ⇒ if we
delete these edges in G 0 we obtain a circulation f in G .
X X
2. f satisfies d(v ) = f (u, v ) − f (v , z) .
(u,v )∈E (v ,z)∈E
| {z } | {z }
edges to v edges out of v

−3
3/ 3 −3
s
1/ 3 2/ 3 1/ 3 2/ 3
G 2/2 G’ 3/ 3 2/ 2
−3 2 −3 2
2/ 2
2/2 2/ 2 2/ 2 2/ 2
4 4 t
4/ 4
Main results

Theorem (Circulation integrality theorem)

If all capacities and demands are integers, and there exists a
circulation, then there exists an integer valued circulation.
Sketch Proof Max-flow formulation + integrality theorem for
max-flow 2
From the previous discussion, we can conclude:
Theorem (Necessary and sufficient condition)
There is a feasible circulation with {d(v )}v ∈V in G iff the
max-flow in G 0 has value D.
Circulations with demands and lower bounds: Max-flow
formulation
Generalization of the previous problem: besides satisfy demands at
nodes, we want to force the flow to use certain edges.
Introduce a new constrain `(e) on each e ∈ E , indicating the
min-value the flow must be on e.
Given G = (V , E ) with c(e), c(e) ≥ `(e) ≥ 0, for each e ∈ E and
{d(v )}v ∈V , define a circulation as a function f : E → R+ s.t.
1. capacity: For each e ∈ E , −3
`(e) ≤ f (e) ≤ c(e), [ 2,3] 3

2. conservation: For each v ∈ V , −3 2 2

X X
f (u, v )− f (v , z) = d(v ). 2 2

(u,v )∈E (v ,z)∈E 4

Circulation problems with lower bounds: Given (G , c, `, {d(v )}),

does there exists a feasible circulation?
Circulations with demands and lower bounds:
Max-flow formulation

Let (G = (V , E ), c, `, d(·)) be a graph, construct

G 0 = (V , E ), c 0 , d 0 ), where for each e = (u, v ) ∈ E , with `(e) > 0:
I c 0 (e) = c(e) − `(e) (sent `(e) units along e).
I Update the demands on both ends of e (d 0 (u) = d(u) + `(e)
and d 0 (v ) = d(v ) − `(e))

−3 −1
[ 2,3] 3 1 3

G −3 2 2 G’ −5 2 2

2 2 2 2
4 4
Main result

Theorem
There exists a circulation in G iff there exists a circulation in G 0 .
Moreover, if all demands, capacities and lower bounds in G are
integers, then there is a circulation in G that is integer-valued.
Sketch Proof Need to prove f (e) is a circulation in G iff
f 0 (e) = f (e) − `(e) is a circulation in G 0 .
The integer-valued circulation part is a consequence of the
integer-value circulation Theorem for f 0 in G 0 . 2
Survey design problem
Problem:Design a survey among customers of products
I Each customer will receive questions about some products.
I Each customer i can only be asked bout a number of products
between ci and ci0 ([ci , ci0 ]) which he has purchased.
I For each product j we want to collect date for a minimum of
pj distinct customers and a maximum of pj0 ([pj , pj0 ])
Survey design problem

Measuring customer satisfaction.

Formally we want to model the problem as:
I A bipartite graph G = (C ∪ P, E ), where C = {i} is the set of
customers and P = {i} is the set of products.
I There is an (i, j) ∈ E is i has purchased product j.
I For each i ∈ {1, . . . , n} we we have bounds [ci , ci0 ] on the
number of products i can be asked about.
I For each j ∈ {1, . . . , n} we we have bounds ([pj , pj0 ]) on the
number of customers that can be asked about it.
Survey design problem: Bipartite graph G

C P
a 1 Customers C={a,b,c,d} a:[1,2] 1: [1,2]
b:[1,3] 2: [1,2]
b 2 Products P={1,2,3,4,5,6} c:[1,2] 3: [1,2]
G
Customer Buys d:[2,4] 4: [1,2]
c 3
a 1,2 5: [0,1]
b 1,2,4 6: [1,2]
d 4
c 3,6
5 d 3,4,5,6

6
Survey design problem: Max flow formulation

We construct G 0 from G , by adding:

Edges: s → {C }, {P} → t, and 0,

(t, s). c,c´ i

0,1
j p,p´

Capacities: c(t, s) = ∞ s t

c(i, j) = 1,
c(s, i) = [ci , ci0 ],
0,1
c(j, t) = [pj , pj0 ].
Notice if f is the flow:
I f (i, j) = 1 ⇒ customer i is asked about product j,
I f (s, i) # products to ask customer i for opinion,
I f (j, t) = # customers to be asked to review product j,
I f (t, s) is the number of questions asked.
Max flow formulation: Example

10

a 1 2
[1,2] 1 1 [1,2] a 1,2 a:[1,2] 1: [1,2]
2 [1,3] 2 [1,2] b 1,2,4 b:[1,3] 2: [1,2]
3 b 1 2 [1,2] t c 3,6 c:[1,2] 3: [1,2]
s 2 1 2 d 3,4,5,6 d:[2,3] 4: [1,2]
1 [1,2]
[1,2] c 3
1 2 [1,2] 5: [0,1]
[2,3] 3 1 6: [1,2]
d 4 [0,1] 1 1
1
1
5

6
Main result

Theorem G 0 has a feasible circulation iff there is a feasible way to

design the survey.
Proof if there is a feasible way to design the survey:
I if i is asked about j then f (i, j) = 1,
I f (s, i) = number questions asked to i,
I f (j, t) = number of customers who were asked about j,
I f (t, s) = total number of questions.
I easy to verify that f is feasible in G 0
If there is an integral, feasible circulation in G 0 :
I if f (i, j) = 1 then i will be asked about j,
I the constrains (ci , ci0 , pj , pj0 ) will be satisfied. 2
Pixels and digital image
I In digital imaging, a pixel is the smallest controllable element
of a picture represented on the screen.
I Digital images are represented by a raster graphics image, a
dot matrix data structure representing rectangular grid of
pixels, or points of color
I The address of a pixel corresponds to its physical coordinates.
Image segmentation

Given a set of pixels classify each pixel as part of the main object
or as part of the background.
Important problem in different techniques for image processing.
Foreground/background segmentation
I We aim to label each pixel as belonging to the foreground or
the background
I Picture pixels as a grid of dots.
I Define the undirected graph G = (V , E ), where, V = set
pixels in image, E = pairs of neighbors of pixels (in the grid)
I For each pixel i, ai ≥ 0 is likelihood that i is in the foreground
and bi ≥ 0 is likelihood that i is in the background.
I For each (i, j) of neighboring pixels, there is a separation
penalty pij ≥ 0 for placing one in the foreground and the
other in the background.
Foreground/background segmentation

Goals:
I For i isolated, if ai > bi we prefer to label i as foreground
(otherwise we label i as background)
I If many neighbors of i are labeled foreground we prefer to
label i as foreground. This makes the labeling smoother by
minimizing the amount of foreground/background
I We want to partition V into A (set of foreground pixels) and
B (set of background pixels), such that we maximize the
objective function:
X X X
ai + bj − pij
i∈A j∈B (i,j)∈E ,|A∩{i,j}|=1
Formulate as a min-cut problem

Segmentation has the flavor of a cut problem, but

I it is a maximization different than the min-cut,
I G is undirected,
I it does not have sink s and source t.
From maximization to minimization
X X X
Recall we want to max( ai + bj − pij )
i∈A j∈B (i,j)∈E ,|A∩{i,j}|=1
| {z }
(∗)
P X X
I Let Q = i∈V (ai + bi ) = bi + aj , then
i∈V j∈V
| {z }
Θ(1)
P P P P
i∈A ai + j∈B bj = Q − ( i∈A bi + j∈B aj )
So, (∗) ≡ Q −
P P P
I i∈A bi − j∈B aj ) − (i,j)∈E ,|A∩{i,j}|=1 pij
I Therefore,
X X X
max(∗) = min bi + aj + pij .
i∈A j∈B (i,j)∈E ,|A∩{i,j}|=1
Transforming G into an s → t network G 0

We transform G = (V , E ) to G 0 = (V 0 , E 0 ) by
I Add a upper node s representing the foreground
I Add a lower node t representing the background
I V 0 = V ∪ {s, t}
I For each (v , u) ∈ E create antiparallel directed edges (u, v )
and (v , u) in E 0
I For each pixel i create directed edges (s, i) and (i, t)
I E 0 = {(s, v ) ∪ (v , t)}v ∈E ∪ {(u, v ) ∪ (v , u)}(u,v )∈E
The undirected pixel graph G and the digraph G 0

G’
Adding capacities to the edges of G 0

I For each i ∈ V , c(s, i) = ai , c(i, t) = bi

I For each (i, j) ∈ E , c(i, j) = c(j, i) = pij

s aw
puw
av

u w
ax
pvu bu pwx

v x
bw

pxv bv t
Min-cut in G 0
An s − t cut (A0 , B 0 ) corresponds to a partition of the pixels into
(A0 − {s}, B 0 − {t}), where
I Edges (s, j) with j ∈ B contributes with aj to c(A0 , B 0 ),
I edges (i, t) where i ∈ A contributes with bj to c(A0 , B 0 ),
I edges (i, j) where i ∈ A and j ∈ B contributes with pij to
c(A0 , B 0 )
Therefore,
X X X
c(A0 , B 0 ) = bi + aj + pij s aw
puw
i∈A j∈B (i,j)∈E ,|A∩{i,j}|=1 av
B0
u w
ax
We want to find the min value of the pvu bu pwx

above quantity, which is equivalent to find v x

bw
the min-cut (A, B) in G 0 ⇒ find the A0

max-flow s − t in G 0 . pxv bv t
Conclusions

Max-Flow/ Min-Cut problem is an intuitively easy problem with

lots of applications.
We just presented a few ones.
An alternative point of view can be obtained from duality in LP
The material in this talk has been basically obtained from two
textbooks:
I Chapter 26 of Cormen, Leiserson, Rivest, Stein: Introduction
to Algorithms, and
I chapter 7 of kleinberg, Tardos: Algorithm Design.