THE UNIVERSITY OF NEW SOUTH WALES
8. MAXIMUM FLOW
Raveen de Silva,
office: K17 202
Course Admin: ,
School of Computer Science and Engineering UNSW Sydney
Term 3, 2021
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem 3. Applications of Network Flow
4. Puzzle
Flow Networks
Definition
A flow network G = (V , E ) is a directed graph in which each edge e = (u,v) ∈ E has a positive integer capacity c(u,v) > 0.
There are two distinguished vertices: a source s and a sink t; no edge leaves the sink and no edge enters the source.
v1
12
v3
16
20
s 104 7 t 9
13 4
v2
14
v4
Flow Networks
Examples of flow networks (possibly with several sources and many sinks):
transportation networks gas pipelines
computer networks
and many more.
Flow Networks
Definition
AflowinG isafunctionf :E →R+,f(u,v)≥0,whichsatisfies 1. Capacity constraint: for all edges e(u,v) ∈ E we require
f(u,v) ≤ c(u,v),
i.e. the flow through any edge does not exceed its capacity.
2. Flow conservation: for all vertices v ∈ V − {s , t } we require f(u,v)= f(v,w),
(u,v )∈E (v ,w )∈E
i.e. the flow into any vertex (other than the source and the sink) equals the flow out of that vertex.
Flow Networks
Definition
The value of a flow is defined as
|f|= f(s,v)= f(v,t),
v:(s,v)∈E v:(v,t)∈E
i.e. the flow leaving the source or equivalently the flow arriving at the sink.
Given a flow network, our goal is to find a flow of maximum value.
Maximum Flow
Integrality Theorem
If all capacities are integers (as we assumed earlier), then there is a flow of maximum value such that f(u,v) is an integer for each edge (u,v) ∈ E.
Note
This means that there is always at least one solution entirely in integers. We will only consider integer solutions hereafter.
Maximum Flow
In the following example, f /c represents f units of flow sent through an edge of capacity c.
v1
12/12
v3
11/16 s
8/13
0/10
1/4
4/9
15/20 7/7 t
4/4
v2
v4
11/14
The pictured flow has a value of 19 units, and it does not appear possible to send another unit of flow. But we can do better!
Maximum Flow
Here is a flow of value 23 units in the same flow network.
v1
12/12
v3
11/16 s
12/13
0/10
1/4
0/9
19/20 7/7 t
4/4
v2
v4
11/14
Maximum Flow
This example demonstrates that the most basic greedy algorithm – send flow one unit at a time along arbitrarily chosen paths – does not always achieve the maximum flow.
What went wrong in the first attempt?
We sent 19 units of flow to vertex v3, only to send four units
back to v2.
It would have been better to send those four units of flow to t directly, but this may not have been obvious at the time this decision was made.
We need a way to correct mistakes! If only we could send flow from v2 back to v3 so as to “cancel out” the earlier allocation …
Residual Flow Network
Recall the last example of a flow.
v1
12/12
v3
11/16 s
12/13
0/10
1/4
0/9
19/20 7/7 t
4/4
v2
v4
11/14
Residual Flow Network
Definition
Given a flow in a flow network, the residual flow network is the network made up of the leftover capacities.
12
v1 51
v3
11 19
s 113 7 t 9
1 12
4
v2
3 11
v4
Residual Flow Network
Suppose the original flow network has an edge from v to w with capacity c, and that f units of flow are being sent through this edge.
The residual flow network has two edges:
1. an edge from v to w with capacity c −f, and 2. an edge from w to v with capacity f .
These capacities represent the amount of additional flow in each direction. Note that sending flow on the “virtual” edge from w to v counteracts the already assigned flow from v to w.
Edgesofcapacityzero(whenf =0orf =c)neednotbe included.
Residual Flow Network
Suppose the original flow network has an edge from v to w with capacity c1 and flow f1 units, and an edge from w to v with capacity c2 and flow f2 units.
What are the corresponding edges in the residual graph? How much flow can be sent from v to w (and vice versa)?
The forward edge allows c1 − f1 additional units of flow, and we can also send up to f2 units to cancel the flow through the reverse edge.
Thus we create edges from v to w with capacity c1 − f1 + f2 and similarly from w to v with capacity c2 − f2 + f1.
Augmenting Paths
Definition
An augmenting path is a path from s to t in the residual flow network.
The residual flow network below corresponds to the earlier example of a flow of value 19 units. An augmenting path is pictured in red.
12 55
v1
11 4 15
v3
s 113 7 t
5
8
5
3 11
4
v2
v4
Augmenting Paths
The capacity of an augmenting path is the capacity of its “bottleneck” edge, i.e., the edge of smallest capacity.
We can now send that amount of flow along the augmenting path, recalculating the flow and the residual capacities for each edge used.
Suppose we have an augmenting path of capacity f , including an edge from v to w. We should:
cancel up to f units of flow being sent from w to v,
add the remainder of these f units to the flow being sent from v to w,
increase the residual capacity from w to v by f , and reduce the residual capacity from v to w by f .
Augmenting Paths
Recall that the augmenting path was as follows.
545
s v2 v3 t 8 5 15
After sending four units of flow along this path, the new residual flow network is pictured below.
12 51
v1
11 0 19
v3
s 113 7 t
1 12
9
3 11
4
v2
v4
Augmenting Paths
The flow used to be as follows.
v1
12/12
v3
11/16 s
8/13
0/10
1/4
4/9
15/20 7/7 t
4/4
v2
v4
11/14
Augmenting Paths
Pictured below is the new flow, after sending four units of flow alongthepaths→v2 →v3 →t.
v1
12/12
v3
11/16 s
12/13
0/10
1/4
0/9
11/20 7/7 t
4/4
v2
v4
11/14
Note that the four units of flow previously sent from v3 to v2 have been cancelled out.
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem 3. Applications of Network Flow
4. Puzzle
Ford-Fulkerson algorithm
Keep adding flow through new augmenting paths for as long as it is possible.
When there are no more augmenting paths, you have achieved the largest possible flow in the network.
Ford-Fulkerson algorithm: Example (1/5)
v1
12
v3
20
s 104 7 t
16
9
13 4
v2
14
4/12
v4
v1
v3
4/16
0/20 0/7 t
4/4
s
0/10
0/4
4/9
0/13
v2
v4
4/14
Ford-Fulkerson algorithm: Example (2/5)
v1
8 4
v3
12
4
20
s 104 7 t
4
5
13 10 4
v2
v4
v1
4
4/12
v3
11/16
7/20 7/7 t
4/4
s
7/10
0/4
0/13
4/9
v2
v4
11/14
Ford-Fulkerson algorithm: Example (3/5)
8
5 4 13
11 4 7
s 311 7 t
v1
v3
5
13 3 4
v2
v4
v1
11
12/12
1/4
v3
11/16
15/20 7/7 t
4/4
s
0/10
8/13
4/9
v2
v4
11/14
Ford-Fulkerson algorithm: Example (4/5)
12 55
v1
11 4 15
v3
s 113 7 t
5
8
5
3 11
12/12
1/4
4
v2
v4
v1
v3
11/16
19/20 7/7 t
4/4
s
0/10
12/13
0/9
v2
v4
11/14
Ford-Fulkerson algorithm: Example (5/5)
v1
12
v3
51
11 19
s 113 7 t
1 12
9
3 11
4
v2
v4
Ford-Fulkerson algorithm
Why does this procedure terminate?
Why can’t we get stuck in a loop, which keeps adding augmenting paths forever?
If all the capacities are integers, then each augmenting path increases the flow through the network by at least 1 unit.
However, the total flow is finite. In particular, it cannot be larger than the sum of all capacities of all edges leaving the source.
We conclude that the process must terminate eventually.
Ford-Fulkerson algorithm
Even if the procedure does terminate, why does it produce a flow of the largest possible value?
Maybe we have created bottlenecks by choosing bad augmenting paths; maybe better choices of augmenting paths could produce a larger total flow through the network?
This is not at all obvious, and to show that this is not the case we need a mathematical proof!
Cuts in a Flow Network
The proof is based on the notion of a minimal cut in a flow network.
Definition
A cut in a flow network is any partition of the vertices of the underlying graph into two subsets S and T such that:
1. S ∪ T = V
2. S ∩ T = ∅
3. s ∈ S and t ∈ T.
Cuts in a Flow Network
Definition
The capacity c(S,T) of a cut (S,T) is the sum of capacities of all edges leaving S and entering T, i.e.
c(S,T)= {c(u,v):u∈S,v∈T}. (u,v)∈E
Note that the capacities of edges going in the opposite direction, i.e. from T to S, do not count.
Cuts in a Flow Network
Definition
Given a flow f, the flow f(S,T) through a cut (S,T) is the total flow through edges from S to T minus the total flow through edges from T to S, i.e.
f(S,T)= {f(u,v):u∈S,v∈T} (u,v)∈E
− {f(u,v):u∈T,v∈S}. (u,v)∈E
Cuts in a Flow Network
Exercise
Prove that for any flow f, the flow through any cut (S,T) is equal to the value of the flow, i.e.
f (S , T ) = |f |.
Hint
Recall the definition of the value of a flow, and use the property of flow conservation.
Cuts in a Flow Network
An edge from S to T counts its full capacity towards c(S,T), but only the flow through it towards f (S , T ).
An edge from T to S counts zero towards c(S,T), but counts the flow through it in the negative towards f (S , T ).
Therefore f (S , T ) ≤ c (S , T ).
It follows that |f | ≤ c (S , T ), so the value of any flow is at most the capacity of any cut.
Cuts in a Flow Network: Example
v1
12/12
v3
11/16 s
8/13
0/10
1/4
4/9
15/20 7/7 t
4/4
v2
v4
11/14 ST
Cuts in a Flow Network: Example
In the above example the net flow across the cut is given by f(S,T) = f(v1,v3)+f(v2,v4)−f(v2,v3) = 12+11−4 = 19.
Note that the flow in the opposite direction (from T to S) is subtracted.
The capacity of the cut c(S,T) is given by
c (S , T ) = c (v1 , v3 ) + c (v2 , v4 ) = 12 + 14 = 26.
As we have mentioned, we add only the capacities of vertices from S to T and not of vertices in the opposite direction.
Theorem
Theorem
The maximal amount of flow in a flow network is equal to the capacity of the cut of minimal capacity.
Let f be a flow. Recall that the value |f | is at most the capacity of any cut: c(S,T).
Thus, if we find a flow f which equals the capacity of some cut (S,T), then such flow must be maximal and the capacity of such a cut must be minimal.
We now show that when the Ford-Fulkerson algorithm terminates, it produces a flow equal to the capacity of an appropriately defined cut.
Ford-
Assume that the Ford-Fulkerson algorithm has terminated, so there no more augmenting paths from the source s to the sink t in the last residual flow network.
Define S to be the source s and all vertices u such that there is a path in the residual flow network from the source s to that vertex u.
Define T to be the set of all vertices for which there is no such path.
Since there are no more augmenting paths from s to t, clearly the sink t belongs to T.
Ford-
v1
12
v3
51
11 19
s 113 7 t
1 12
9 3
v4
11 S
4
T
v2
v1
12/12
1/4
11/14
v3
11/16
19/20 7/7 t
s
0/10
0/9
12/13
4/4 T
S
v2
v4
Ford-
Claim
All the edges from S to T are fully occupied with flow, and all the edges from T to S are empty.
ST
3/5 uv 2
6/9 xy 6
Ford-
Proof
Suppose an edge (u, v ) from S to T has any additional capacity left. Then in the residual flow network, the path from s to u could be extended to a path from s to v. This contradicts our assumption that v ∈ T .
Suppose an edge (y,x) from T to S has any flow in it. Then in the residual flow network, the path from s to x could be ex- tended to a path from s to y. This contradicts our assumption that y ∈ T.
Ford-
Since all edges from S to T are occupied with flows to their full capacity, and also there is no flow from T to S, the flow across the cut (S,T) is precisely equal to the capacity of this cut, i.e., f (S , T ) = c (S , T ).
Thus, such a flow is maximal and the corresponding cut is a minimal cut, regardless of the particular way in which the augmenting paths were chosen.
Ford-
How efficient is the Ford-Fulkerson algorithm?
vv
0/1000 0/1000
s 0/1 t s 1 t
1000 1000
0/1000
1/1000
0/1000 1000 1000 ww
vv
0/1000 999
1000
1
s 1/1 t s 1 t
0/1000 1/1000 1000 ww
999
1
Ford-
vv
1/1000 1/1000 999
s 0/1 t s 1 t
999
11 1/1000 999 999
ww
vv
11
1/1000
1/1000 998
s 1/1 t s 1 t
2/1000
999
21 12
1/1000 2/1000 999 998 ww
The Ford-Fulkerson algorithm can potentially run in time proportional to the value of the max flow, which can be exponential in the size of the input.
Edmonds-
The Edmonds-Karp algorithm improves the Ford-Fulkerson algorithm in a simple way: always choose the shortest path from the source s to the sink t, where the “shortest path” means the fewest number of edges, regardless of their capacities (i.e., each edge has the same unit weight).
Note that this choice is somewhat counter intuitive: we preferably take edges with small capacities over edges with large capacities, for as long as they are along a shortest path from s to t.
Edmonds-
Why does such a choice speed up the Ford-Fulkerson algorithm? One can prove that this algorithm runs in time O(|V| |E|2). The proof is not obvious, and can be found in CLRS (pp.727–730).
The fastest max flow algorithm to date is an extension of the Preflow-Push algorithm and runs in time |V|3.
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem 3. Applications of Network Flow
4. Puzzle
Networks with multiple sources and sinks
Flow networks with multiple sources and sinks are reducible to networks with a single source and single sink by adding a “super-source” and “super-sink” and connecting them to all sources and sinks, respectively, by edges of infinite capacity.
s1 t1 ∞∞
s ∞ s2 t ∞ t 2
∞∞
s3 t3
Networks with vertex capacities
Sometimes not only the edges but also the vertices vi of the flow graph might have capacities C(vi), which limit the total throughput of the flow coming to the vertex (and, consequently, also leaving the vertex):
f(u,v)= f(v,w)≤C(v). e(u,v)∈E e(v,w)∈E
We can handle this by reducing it to a situation with only edge capacities!
Networks with vertex capacities
Suppose vertex v has capacity C(v). Split v into two vertices vin and vout.
Attach all of v’s incoming edges to vin and all its outgoing edges from vout.
Connect vin and vout with an edge e∗ = (vin,vout) of capacity C(v).
Networks with vertex capacities
v vin
C(v)
vout
Applications of
Problem
Instance: Suppose you have a movie rental agency.
At the moment you have k movies in stock, with mi copies of
movie i.
There are n customers, who have each specified which subset of the k movies they are willing to see. However, no customer can rent out more than 5 movies at a time.
Task: Dispatch the largest possible number of movies.
Applications of
u1 5
1
v1
m1
v2
m2
5 u2 st
5
m3
. mk
.
1 vk
.
un
v3
Applications of
Problem
Instance: The storage space of a ship is in the form of a rectangular grid of cells with n rows and m columns. Some of the cells are taken by support pillars and cannot be used for storage, so they have 0 capacity.
You are given the capacity of every cell; cell in row ri and column cj has capacity C(i,j). To ensure the stability of the ship, the total weight in each row ri must not exceed Cr(i) and the total weight in each column cj must not exceed Cc(j).
Task: Allocate cargo weight to the cells to maximise the total load without exceeding the limits per column, limits per row and limits per available cell.
Applications of
c1
c2
c3
c4
row cap
r1
C(1,1)
C(1,2)
C(1,3)
C(1,4)
Cr (1)
r2
C(2,1)
C(2,2)
C(2,3)
C(2,4)
Cr (2)
r3
C(3,1)
C(3,2)
0
C(3,4)
Cr (3)
r4
C(4,1)
0
C(4,3)
0
Cr (4)
r5 col cap
C(5,1) Cc (1)
C(5,2) Cc (2)
0 Cc (3)
C(5,4) Cc (4)
Cr (5)
Applications of
r1
Cr(1) r sr3
C(1,1)
c1
Cc(1)
2
c2
t
Cr (5)
r4 r5
Cc (4) c4
c3
C(5,4)
Applications of
Problem
Instance: You are given a connected, directed graph G with N vertices. Out of these N vertices k are painted red, m are painted blue, and the remaining N − k − m > 0 of the vertices are black. Red vertices have only outgoing edges and blue vertices have only incoming edges.
Task: Determine the largest possible number of disjoint (i.e., non-intersecting) paths in this graph, each of which starts at a red vertex and finishes at a blue vertex.
Bipartite Graphs
Definition
A graph G = (V,E) is said to be bipartite if its vertices can be divided into two disjoint sets A and B such that every edge e ∈ E has one end in the set A and the other in the set B.
Matchings
Definition
A matching in a graph G = (V , E ) is a subset M ⊆ E such that each vertex of the graph belongs to at most one edge in M.
A maximum matching in G is a matching containing the largest possible number of edges.
Matchings in a Bipartite Graph
a1
a2
a3
a4
a5
b1
b2
b3
b4
Matchings in a Bipartite Graph
a1
a2
a3
a4
a5
b1
b2
b3
b4
Matchings in a Bipartite Graph
a1
a2
a3
a4
a5
b1
b2
b3
b4
Maximum Bipartite Matching
Problem
Given a bipartite graph G, find the size (i.e. the number of pairs matched) in a maximum matching.
Question
How can we turn a Maximum Bipartite Matching problem into a Maximum Flow problem?
Maximum Bipartite Matching
Answer
Create two new vertices, s and t (the source and sink). Construct an edge from s to each vertex in A, and from each vertex in B to t. Orient the existing edges from A to B. Assign capacity 1 to all edges.
Maximum Bipartite Matching
a1
a2
sa3
a4
a5
b1
b2
b3
b4
t
Maximum Bipartite Matching
Property
Recall that for each edge e = (v , w ) of the flow network, with capacity c and carrying f units of flow, we record two edges in the residual graph:
an edge from v to w with capacity c −f an edge from w to v with capacity f .
Since all capacities in the flow network are 1, we need only denote the direction of the edge in the residual graph!
As always, the residual graph allows us to correct mistakes and increase the total flow.
Maximum Bipartite Matching
a1
a2
sa3
a4
a5
b1
b2
b3
b4
a1
a2
ta3 a4 a5
b1
b2
b3
b4
Maximum Bipartite Matching
a1
a2
sa3
a4
a5
b1
b2
b3
b4
a1
a2
ta3 a4 a5
b1
b2
b3
b4
Maximum Bipartite Matching
a1
a2
sa3
a4
a5
b1
b2
b3
b4
a1
a2
ta3 a4 a5
b1
b2
b3
b4
Maximum Bipartite Matching
a1
a2
sa3
a4
a5
b1
b2
b3
b4
t
Job Centre
Problem
Instance: You are running a job centre. In your country, there are k recognised qualifications. There are n unemployed people, each holding a subset of the available qualifications. There are also m job openings, each requiring a subset of the qualifications.
Task: Place as many people as possible into jobs for which they are qualified. No worker can take more than one job, and no job can employ more than one worker.
Job Centre
Solution
Create an unweighted, undirected graph with vertices a1, . . . , an and b1, . . . , bm, representing the workers and jobs respectively.
Foreach1≤i≤nand1≤j≤m,placeanedgebetweenai and bj if and only if the ith worker holds all qualifications required for the jth job. It is clear that the resulting graph is bipartite.
Consider a matching in this graph. Each of the selected edges corresponds to the placement of a worker in a job, and we correctly ensure that no worker or job is assigned more than once.
Therefore the optimal assignment is exactly the maximum matching in this graph!
Table of Contents
1. Flow Networks
2. Solving the Maximum Flow Problem 3. Applications of Network Flow
4. Puzzle
PUZZLE!!
You are taking two kinds of medicines, A and B; pills of A are completely indistinguishable from pills of B. You take one of each every day and they both come in supply of 30 pills. One day you drop both bottles on the floor and you see that 3 pills have fallen on the floor but you do not know how many from each bottle and you cannot tell which ones (if any) are of type A and which are of type B. How can you solve the problem of continuing to take 1 of each every day without throwing away any pills?
That’s All, Folks!!