Maximum Flow / Minimum Cut
Carlos Anı́bal Suárez
FCNM
ESPOL
1/1
Flow Networks
Network flow
Directed graph with 2 distinguished vertices: source s and
sink t.
Each edge (i, j) has a nonnegative capacity ci,j
2/1
Flow Networks
Maximum flow problem
Given a network flow, maximize the net flow out of the source
s such that the following constraints are satisfied
Capacity constraint: flow fij via (i, j) satisfies 0 ≤ fij ≤ cij
where cij is the capacity of edge (i, j).
Flow conservation: the flow entering a node i is equal to the
flow exiting i where i 6= s, t.
The value of a flow is the net flow out of the source.
Note: the net flow out of the source is equal to the net flow
entering the sink t (by flow conservation)
3/1
Flow Networks
Maximum flow problem
Each edge shows the current flow and the maximum capacity.
current flow via an edge: in front of the colon
capacity of the edge: after the colon
4/1
Flow Networks
Feasible flow
All capacity constraints are met.
Flow conservation is maintained.
5/1
Flow Networks
Infeasible flow
One of the properties is not met.
6/1
Flow Networks
Infeasible flow
One of the properties is not met.
Note: zero is a valid flow so at least one feasible flow always exits
6/1
Flow Networks
Flow cancellation
Positive flow goes either from u to v or from v to u.
Consider the flow as a rate, not a quantity.
Note: another formulation could be skew symmetric : fij = −fji
7/1
Flow Networks
Linear optimization formulation
max fs1 + fs2
fs1 = f12 + f1t
fs2 + f12 = f2t
0 ≤ fs1 ≤ 4
0 ≤ fs2 ≤ 1
0 ≤ f12 ≤ 4
0 ≤ f1t ≤ 1
0 ≤ f2t ≤ 2
8/1
Flow Networks
Linear optimization formulation
P
max fsi
i
P P
fij − fji = 0 for i 6= s or t.
j j
0 ≤ fij ≤ cij for all (i, j)
9/1
Flow Networks
Linear optimization formulation
P
max fsi
i
P P
fij − fji = 0 for i 6= s or t.
j j
0 ≤ fij ≤ cij for all (i, j)
Note: always feasible since fij = 0 for all (i, j) is a feasible flow
9/1
Ford-Fulkerson algorithm
Residual network
given a simple path p from s to t on a network G = (V , E ) of
capacity c, and a feasible flow of value f along p, the residual
network G f (V , E f ) is obtained by updating c to c f where:
10 / 1
Ford-Fulkerson algorithm
Residual network
given a simple path p from s to t on a network G = (V , E ) of
capacity c, and a feasible flow of value f along p, the residual
network G f (V , E f ) is obtained by updating c to c f where:
cijf = cij if i and j are not two adjacent vertices on p
cijf = cij − f (forward capacity) and cjif = cji + f (backward
capacity) if i is the predecessor of j on p
10 / 1
Ford-Fulkerson algorithm
Residual network
given a simple path p from s to t on a network G = (V , E ) of
capacity c, and a feasible flow of value f along p, the residual
network G f (V , E f ) is obtained by updating c to c f where:
cijf = cij if i and j are not two adjacent vertices on p
cijf = cij − f (forward capacity) and cjif = cji + f (backward
capacity) if i is the predecessor of j on p
Note that if the edge j → i was missing (i.e. cji = 0), this
back-edge is added to G f . Similarly, if cijf = 0 the edge i → j
is removed from G f .
10 / 1
Ford-Fulkerson algorithm
Augmenting path
Any simple path p from s to t with a positive feasible flow f
along p in a (residual) network flow is an augmenting path.
11 / 1
Ford-Fulkerson algorithm
Augmenting path
Any simple path p from s to t with a positive feasible flow f
along p in a (residual) network flow is an augmenting path.
the bottleneck capacity along p:
c(p) = min cij
edge ij∈p
11 / 1
Ford-Fulkerson algorithm
Augmenting path
Any simple path p from s to t with a positive feasible flow f
along p in a (residual) network flow is an augmenting path.
the bottleneck capacity along p:
c(p) = min cij
edge ij∈p
For any augmenting path p in a (residual) network, consider
the residual network G f (V , E f ) with f = c(p) along path p
11 / 1
Ford-Fulkerson algorithm
Ford-Fulkerson algorithm
input : initial graph G = (V , E ) with capacity c. It can be
viewed as a the initial residual network flow G 0 with empty
flow
as long as there an augmenting path p in the currently
residual network flow, increase the estimate for the maximal
flow by c(p) and replace the current residual flow the residual
network flow associated to p
Similar in spirit with the Simplex method: at each iteration
the feasible solution is improved until optimality is reached
(the current graph and the associated capacity is updated
while the estimate for the maximal flow is monotonically
increasing)
12 / 1
Ford-Fulkerson algorithm
Ford-Fulkerson algorithm
Ford-Fulkerson Algorithm:
Initialize the value of the flow to 0.
Find any augmenting path p and add c(p) to the flow and
update the residual network flow using p and c(p)
Iterate previous step until there are no more augmenting paths
(i.e. s and t became disconnected)
Augmenting path property: A flow is a maximum flow from s to
t if and only if there is no augmenting path from s to t in the
residual network.
13 / 1
Ford-Fulkerson algorithm
Initial Network : empty flow (f = 0)
14 / 1
Ford-Fulkerson algorithm
Initial augmenting path p: update f to 0 + c(p) = 1
15 / 1
Ford-Fulkerson algorithm
Update the network to (V , E f ) with f = c(p) along p
16 / 1
Ford-Fulkerson algorithm
Next augmenting path p: update f to 1 + c(p) = 4
17 / 1
Ford-Fulkerson algorithm
Update the network to (V , E f ) with f = c(p) along p
18 / 1
Ford-Fulkerson algorithm
INext augmenting path p: update f to 4 + c(p) = 6
19 / 1
Ford-Fulkerson algorithm
Update the network to (V , E f ) with f = c(p) along p
20 / 1
Ford-Fulkerson algorithm
Update the network to (V , E f ) with f = c(p) along p
No more augmenting path : s and t are disconnected ⇒ terminate
20 / 1
Ford-Fulkerson algorithm
No more augmenting path : ⇒ terminate at f = 6
Summing up the augmenting path, the maxflow is equal to 6
21 / 1
Ford-Fulkerson algorithm
Ford-Fulkerson algorithm
If a good augmentation path is found, the algorithm can be
efficient.
small number of remaining edges?
augmentation path with large capacity c f (p)?
The algorithm can be very inefficient if bad augmenting paths
are chosen (exponential exemple)
Is the algorithm finite (assuming all capacities are integers)?
22 / 1
Minimum cut
Cut in a network flow graph
A cut in a network flow is a partition of nodes into two parts,
S and T , such that s ∈ S, and t ∈ T .
Duality between maxflow and mincut problem
(linear optimization duality).
23 / 1
Minimum cut
Cut capacity
The edges of the cut (S, T ) are the edges (i, j) with i ∈ S
and ending in T .
The capacity of the cut (S, T ) is the sum of the capacity of
the edges of the cut.
24 / 1
Minimum cut
Cut capacity
The capacity of the cut (S, T ) is the max flow that can be
sent from S to T .
The capacity of every s-t cut is at least the value of the
maximum flow.
All flow from s to t must at some point cross from S to T .
Hence, it provides an upper bound on the amount of flow
from s to t.
25 / 1
Minimum cut
Cup capacity and maximum flow
Theorem. The value of any flow is bounded above by the capacity
of any cut.
Proof:
|f | = f (S, T )
XX
= f (u, v )
u∈S v ∈T
XX
≤ c(u, v )
u∈S v ∈T
= c(S, T )
26 / 1
Minimum cut
Maxflow / mincut theorem
Theorem. The maximum value over all s − t flows is equal to the
minimum capacity over all s − t cuts.
27 / 1
Minimum cut
Maxflow / mincut theorem reformulation
Reformulation of the maxflow / mincut.
The following are equivalent:
1 |f | = c(S, T ) for some cut (S, T )
2 f is a maximum flow
3 f admits no augmenting paths
Proof:
(1) → (2), since |f | ≤ c(S, T ) for any cut (S, T ), the assumption
that |f | = c(S, T ) implies that f is a maximum flow.
(2) → (3), if there were an augmenting path, the current flow can
be increased, contradicting the maximality of f .
28 / 1
Minimum cut
Maxflow / mincut theorem reformulation
(3) → (1), suppose that f admits no augmenting paths. Define
S = {v ∈ V : there exists a path in G f from s to v } and let
T = V − S. Since s ∈ S and t ∈ T , thus (S, T ) is a cut. Consider
any vertices u ∈ S and v ∈ T .
c f (u, v ) = 0 since if c f (u, v ) > 0, then v ∈ S not v ∈ T as
assumed. Thus f (u, v ) = c(u, v ), since
c f (u, v ) = c(u, v ) − f (u, v ). Summing over all u ∈ S and v ∈ T
yields f (S, T ) = c(S, T ) and since |f | = f (S, T ), the theorem
follows.
29 / 1
Minimum cut
Application : solving s, t mincut
1 Run Ford-Fulkerson algorithm .
2 The set of vertices that are reachable from the the source s in
the last residual graph form S.
30 / 1
Minimum cut
Application : solving s, t mincut
31 / 1
Minimum cut
Application : solving s, t mincut
Maximum flow obtained by Ford-Fulkerson:
32 / 1
Minimum cut
Application : solving s, t mincut
Last residual network (s and t are disconnected):
33 / 1
Minimum cut
Application : solving s, t mincut
Vertices reachable form s form S
34 / 1
Minimum cut
Application : solving s, t mincut
The capacity of the mincut is 3 + 1 + 2 = 6
35 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm
Edmonds-Karp is identical to Ford-Fulkerson with one
important difference: augmenting paths are found using a
specific rule.
36 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm
Edmonds-Karp is identical to Ford-Fulkerson with one
important difference: augmenting paths are found using a
specific rule.
Augmenting paths are found by using BFS where each edge
weight is set to 1 (i.e. capacities are ignored, just select paths
using the minimum number of edges).
36 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm
Edmonds-Karp is identical to Ford-Fulkerson with one
important difference: augmenting paths are found using a
specific rule.
Augmenting paths are found by using BFS where each edge
weight is set to 1 (i.e. capacities are ignored, just select paths
using the minimum number of edges).
Only O(VE ) augmenting paths are required to reach a
maximal flow.
36 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm
Edmonds-Karp is identical to Ford-Fulkerson with one
important difference: augmenting paths are found using a
specific rule.
Augmenting paths are found by using BFS where each edge
weight is set to 1 (i.e. capacities are ignored, just select paths
using the minimum number of edges).
Only O(VE ) augmenting paths are required to reach a
maximal flow.
As augmenting path can be found in O(E ) time, the overall
running time is O(VE 2 ).
36 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm analysis
Lemma. δ(v ) = δ f (s, v ): breath-first distance from s to v in G f .
During the Edmonds-Karp algorithm, δ(v ) increases monotonically.
Proof: Suppose that augmenting a flow produces a new flow f 0 .
0
Let δ 0 (v ) = δ f (s, v ). By induction on δ 0 (v ), we can show that
δ 0 (v ) ≥ δ(v ).
Base case: δ 0 (v ) = 0 implies v = s, and since δ(s) = 0,
δ 0 (v ) ≥ δ(v ).
Inductive case: Consider a breadth-first path s → ... → u → v in
0
G f . δ 0 (v ) = δ 0 (u) + 1 must be true since subpaths of a shortest
path is a shortest path. Hence, δ 0 (u) ≥ δ(u) by induction because
δ 0 (v ) > δ 0 (u).
0
While we have (u, v ) ∈ E f , we must consider two subcases:
(u, v ) ∈/ E f (nondecreasing) or (u, v ) ∈ E f (increasing by ≥ 2)
37 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm analysis
Theorem. Edmonds-Karp: O(VE ) flow augmentations.
38 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm analysis
Theorem. Edmonds-Karp: O(VE ) flow augmentations.
Proof: Let p be an augmenting path and(u, v ) an edge of p. If
c(u, v ) = c(p), then (u, v ) ∈/ E f and (u, v ) is called a critical edge.
(i.e. (u, v ) disappears after the flow augmentation)
38 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm analysis
Theorem. Edmonds-Karp: O(VE ) flow augmentations.
Proof: Let p be an augmenting path and(u, v ) an edge of p. If
c(u, v ) = c(p), then (u, v ) ∈/ E f and (u, v ) is called a critical edge.
(i.e. (u, v ) disappears after the flow augmentation)
The first time (u, v ) is critical, we have δ(v ) = δ(u) + 1 since p is
a breadth-first path. Then, (u, v ) can only be critical again when
(v , u) is again on an augmenting path. Let δ 0 be the distance
function when (v , u) is on an augmenting path.
38 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm analysis
Theorem. Edmonds-Karp: O(VE ) flow augmentations.
Proof: Let p be an augmenting path and(u, v ) an edge of p. If
c(u, v ) = c(p), then (u, v ) ∈/ E f and (u, v ) is called a critical edge.
(i.e. (u, v ) disappears after the flow augmentation)
The first time (u, v ) is critical, we have δ(v ) = δ(u) + 1 since p is
a breadth-first path. Then, (u, v ) can only be critical again when
(v , u) is again on an augmenting path. Let δ 0 be the distance
function when (v , u) is on an augmenting path.
δ 0 (u) = δ 0 (v ) + 1 (breadth-first search)
≥ δ(v ) + 1 (monotonicity)
= δ(u) + 2 (breadth-first path)
38 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm analysis
Theorem. Edmonds-Karp: O(VE ) flow augmentations
Distances start out nonnegative, never decrease, and are at most
|V | − 1 until the vertex becomes unreachable. Thus, (u, v ) occurs
as a critical edge O(V ) times because δ(v ) increases by at least 2
between occurrences. Since the residual graph contains O(E )
edges, the number of flow augmentations is O(VE ).
39 / 1
Edmonds-Karp Algorithm
Edmonds-Karp algorithm analysis
Theorem. Edmonds-Karp: O(VE ) flow augmentations
Distances start out nonnegative, never decrease, and are at most
|V | − 1 until the vertex becomes unreachable. Thus, (u, v ) occurs
as a critical edge O(V ) times because δ(v ) increases by at least 2
between occurrences. Since the residual graph contains O(E )
edges, the number of flow augmentations is O(VE ).
Corollary. Edmonds-Karp algorithm runs in O(VE 2 ) time.
39 / 1
Applications
Edge-disjoint paths
A set of paths in a directed path G between two vertices s
and t is edge-disjoint if each edge appears in at most one of
the paths. Multiple edge-disjoint paths may pass through the
same vertex.
Set each edge capacity to 1, and solve the maxflow problem.
The maxflow value is equal to the number of edge-disjoint
paths.
To extract paths, find a directed path from s to t, remove it,
and recurse.
40 / 1
Applications
Modification: vertex capacities
Can vertices have a capacity constraint as well?
In addition to edge constraints, there is the additional
requirement that each vertex v , with 6= s and v 6= t, has some
nonnegative value denoting the maximum total flow traversing
vertex v .
41 / 1
Applications
Modification: vertex capacities
Can vertices have a capacity constraint as well?
In addition to edge constraints, there is the additional
requirement that each vertex v , with 6= s and v 6= t, has some
nonnegative value denoting the maximum total flow traversing
vertex v .
Model as a flow network with only edge constraints. Replace
such vertex v by 2 vertices vin and vout . Connect vin and vout .
by an edge with capacity equal to given capacity of v . All
edges going into v are updated to go into vin , and all edges
going out of v are updated to go out from vout .
41 / 1
Applications
Modification: vertex capacities
Can vertices have a capacity constraint as well?
In addition to edge constraints, there is the additional
requirement that each vertex v , with 6= s and v 6= t, has some
nonnegative value denoting the maximum total flow traversing
vertex v .
Model as a flow network with only edge constraints. Replace
such vertex v by 2 vertices vin and vout . Connect vin and vout .
by an edge with capacity equal to given capacity of v . All
edges going into v are updated to go into vin , and all edges
going out of v are updated to go out from vout .
Application: the calculation of vertex-disjoint paths from s to t
(set the capacity of each vertex to 1).
41 / 1
Applications
Modification: multi-sources, multi-sinks and application
Set of jobs, J = {J1 , J2 , ...Jn } and available time-slots,
T = {T1 , T2 , ...Tn } when jobs can be performed.
Each job J has a set of valid slots, Sj ⊆ T , when it can be
scheduled.
Constraint is that no two jobs can be scheduled during the
same time-slot. What is the largest set of jobs that can be
scheduled?
Reduce the problem to a bipartite matching problem: Each
job is a source-node in X , each time-slot is a sink-node in Y ,
and every time-slot T in Sj , creates an edge between J and T .
Create a dummy source which connects to every source-node
in X and a dummy sink which is connected to by every
sink-node in Y . Solve using max flow algorithm.
42 / 1