64 Max Flow

Algorithms R OBERT S EDGEWICK | K EVIN W AYNE
6.4 M AXIMUM F LOW

‣ introduction
‣ Ford-Fulkerson algorithm
‣ maxflow-mincut theorem
Algorithms
‣ analysis of running time
F O U R T H E D I T I O N
R OBERT S EDGEWICK | K EVIN W AYNE

‣ Java implementation
http://algs4.cs.princeton.edu ‣ applications
6.4 M AXIMUM F LOW
‣ introduction
Algorithms

Mincut problem
Input. An edge-weighted digraph, source vertex s, and target vertex t.
each edge has a

positive capacity
capacity
4 15 15 10
10
s 5 8 10 t
15
4 6 15 10
16
3
Mincut problem
Def. A st-cut (cut) is a partition of the vertices into two disjoint sets,
with s in one set A and t in the other set B.
Def. Its capacity is the sum of the capacities of the edges from A to B.
10
s 5 t
15
capacity = 10 + 5 + 15 = 30
4
Mincut problem
10
s 8 t
don't count edges

from B to A
16
capacity = 10 + 8 + 16 = 34
5
Mincut problem
Minimum st-cut (mincut) problem. Find a cut of minimum capacity.
10
s 8 t
10
capacity = 10 + 8 + 10 = 28
6
Mincut application (RAND 1950s)
"Free world" goal. Cut supplies (if cold war turns into real war).
rail network connecting Soviet Union with Eastern European countries

(map declassified by Pentagon in 1999)
Figure 2
7
From Harris and Ross [1955]: Schematic diagram of the railway network of the Western So-
Potential mincut application (2010s)
Government-in-power’s goal. Cut off communication to set of people.
8
Maxflow problem
Input. An edge-weighted digraph, source vertex s, and target vertex t.
each edge has a

positive capacity
capacity
15 15 10
4
10
s 5 8 10 t
15
6 15 10
4
16
9
Maxflow problem
Def. An st-flow (flow) is an assignment of values to the edges such that:

・Capacity constraint: 0 ≤ edge's flow ≤ edge's capacity.
・Local equilibrium: inflow = outflow at every vertex (except s and t).
flow capacity
inflow at v = 5 + 5 + 0 = 10
5/9 outflow at v = 10 + 0 = 10
5 5
10 0/4 /1 0 / 15 /
10
/ 5
10
s 5/5 5/8 v 10 / 10 t
10
/ 0 0 / 15 10
15 0/4 /6 /
10
10 / 16
10
Maxflow problem

Def. The value of a flow is the inflow at t.
we assume no edges point to s or from t
5/9
5 5
10 0/4 /1 0 / 15 /
10
/ 5
10
s 5/5 5/8 10 / 10 t value = 5 + 10 + 10 = 25
10
/ 0 0 / 15 10
15 0/4 /6 /
10
10 / 16
11
Maxflow problem

Def. The value of a flow is the inflow at t.
Maximum st-flow (maxflow) problem. Find a flow of maximum value.
8/9
2 8
10 0/4 /1 0 / 15 /
10
/ 5
10
s 5/5 8/8 10 / 10 t value = 8 + 10 + 10 = 28
13
/ 3 0 / 15 10
15 0/4 /6 /
10
13 / 16
12
Maxflow application (Tolstoǐ 1930s)
Soviet Union goal. Maximize flow of supplies to Eastern Europe.
flow
capacity
rail network connecting Soviet Union with Eastern European countries

(map declassified by Pentagon
Figure 2 in 1999)
13
From Harris and Ross [1955]: Schematic diagram of the railway network of the Western So-
Potential maxflow application (2010s)
"Free world" goal. Maximize flow of information to specified set of people.
facebook graph
14
Summary
Input. A weighted digraph, source vertex s, and target vertex t.

Mincut problem. Find a cut of minimum capacity.
Maxflow problem. Find a flow of maximum value.
8/9
2 8
/1 /
10 0/4 5 0 / 15 10 10
/
10
s 5/5 8/8 10 / 10 t s 8 t
13
/ 3 10
15 0/4 /6 0 / 15
/ 10
10
13 / 16
value of flow = 28 capacity of cut = 28
Remarkable fact. These two problems are dual!

15
6.4 M AXIMUM F LOW
‣ introduction
Algorithms

Ford-Fulkerson algorithm
Initialization. Start with 0 flow.
flow capacity
initialization
0/9
0
0 /
10 0/4 /1 0 / 15 10
/ 5
0 value of flow
s 0/5 0/8 0 / 10 t 0
0
/ 0 10
15 0/4 /6 0 / 15 /
0
0 / 16
17
Idea: increase flow along augmenting paths
Augmenting path. Find an undirected path from s to t such that:

・Can increase flow on forward edges (not full).
・Can decrease flow on backward edge (not empty).
1st augmenting path
bottleneck capacity = 10
0/9
10
— 0
0 /
10 / 10 0/4 /1 0 / 15 10
0
— 5
10
s 0/5 0/8 —
0 / 10 t 0 + 10 = 10
0
/ 0 10
15 0/4 /6 0 / 15 /
0
0 / 16
18

2nd augmenting path
0/9
10 0
10 0/4 0 / 15 /
/ /1 10
5
10
s 0/5 0/8 10 / 10 t 10 + 10 = 20
10
—
0
/ 0 10 10
15 0/4 /6 0 / 15 /
0
—
10
—0 / 16
19

3rd augmenting path
backward edge
5
—
0/9 (not empty)
5 5
1—0 —
0
10 0/4 0 / 15 /
/ /1 10
5
10
5 5
s —
0/5 —
0/8 10 / 10 t 20 + 5 = 25
10 10
/ 0/4 0 0 / 15 /
15 /6 10
10 / 16
20

4th augmenting path
backward edge
8
—
5/9 (not empty)
2 8
—
5
—
5 /
10 0/4 /1 0 / 15 10
/ 5
10
8
s 5/5 —
5/8 10 / 10 t 25 + 3 = 28
13
3
1—0 10
/ 0/4 —
0 0 / 15 /
15 /6 10
13
10
— / 16
21
Termination. All paths from s to t are blocked by either a

・Full forward edge.
・Empty backward edge.
no more augmenting paths
8/9
2 8
10 0/4 /1 0 / 15 /
/ 10
5
10
s 5/5 8/8 10 / 10 t 28
13 10
/ 0/4 3 0 / 15 /
15 /6 10
full forward edge

13 / 16 empty backward edge
22
Start with 0 flow.

While there exists an augmenting path:
- find an augmenting path
- compute bottleneck capacity
- increase flow on that path by bottleneck capacity
Questions.
・How to compute a mincut?
・How to find an augmenting path?
・If FF terminates, does it always compute a maxflow?
・Does FF always terminate? If so, after how many augmentations?
23
6.4 M AXIMUM F LOW
‣ introduction
Algorithms

Relationship between flows and cuts
Def. The net flow across a cut (A, B) is the sum of the flows on its edges
from A to B minus the sum of the flows on its edges from B to A.
net flow across cut = 5 + 10 + 10 = 25
5/9
5 5
10 0/4 /1 0 / 15 /
10
/ 5
10
s 5/5 5/8 10 / 10 t value of flow = 25
10
/ 0 0 / 15 10
15 0/4 /6 /
10
10 / 16
25
net flow across cut = 10 + 5 + 10 = 25
5/9
5 5
10 0/4 /1 0 / 15 /
10
/ 5
10
s 5/5 5/8 10 / 10 t value of flow = 25
10
/ 0 0 / 15 10
15 0/4 /6 /
10
10 / 16
26
net flow across cut = (10 + 10 + 5 + 10 + 0 + 0) – (5 + 5 + 0 + 0) = 25
5/9
edges from B to A
5 5
10 0/4 /1 0 / 15 /
10
/ 5
10
s 5/5 5/8 10 / 10 t value of flow = 25
10
/ 0 0 / 15 10
15 0/4 /6 /
10
10 / 16
27
Flow-value lemma. Let f be any flow and let (A, B) be any cut. Then, the net
flow across (A, B) equals the value of f.
Intuition. Conservation of flow.
Pf. By induction on the size of B.

・Base case: B = { t }.
・Induction step: remains true by local equilibrium when moving
any vertex from A to B.
Corollary. Outflow from s = inflow to t = value of flow.
28
Weak duality. Let f be any flow and let (A, B) be any cut.
Then, the value of the flow ≤ the capacity of the cut.
Pf. Value of flow f = net flow across cut (A, B) ≤ capacity of cut (A, B).
flow-value lemma flow bounded by capacity
8/9
2 8
/1 /
10 0/4 5 0 / 15 10
/ 10
10
s 5/5 7/8 9 / 10 t s 5 t
12
/ 2
15 0/4 /6 0 / 15 10 15
/
10
12 / 16
value of flow = 27 capacity of cut = 30

29
Maxflow-mincut theorem
Augmenting path theorem. A flow f is a maxflow iff no augmenting paths.

Maxflow-mincut theorem. Value of the maxflow = capacity of mincut.
Pf. The following three conditions are equivalent for any flow f :
i. There exists a cut whose capacity equals the value of the flow f.
ii. f is a maxflow.
iii. There is no augmenting path with respect to f.
[i ii ]
・Suppose that (A, B) is a cut with capacity equal to the value of f.
・Then, the value of any flow f ' ≤ capacity of (A, B) = value of f.
・Thus, f is a maxflow. weak duality by assumption
30

ii. f is a maxflow.
[ ii iii ] We prove contrapositive: ~iii ~ii.

・Suppose that there is an augmenting path with respect to f.
・Can improve flow f by sending flow along this path.
・Thus, f is not a maxflow.
31

ii. f is a maxflow.
[ iii i]
Suppose that there is no augmenting path with respect to f.
・Let (A, B) be a cut where A is the set of vertices connected to s by an
undirected path with no full forward or empty backward edges.
・By definition of cut, s is in A.
・Since no augmenting path, t is in B.
・Capacity of cut = net flow across cut forward edges full; backward edges empty
= value of flow f. flow-value lemma
32
Computing a mincut from a maxflow
To compute mincut (A, B) from maxflow f :

・By augmenting path theorem, no augmenting paths with respect to f.
・Compute A = set of vertices connected to s by an undirected path
with no full forward or empty backward edges.
8/9
2 8
/
10 0/4
/1 0 / 15 10
/ 5
10
s 5/5 8/8 10 / 10 t
A 13
/ 3/4 6 10
15 /6 0 / 15 /
10
full forward edge

forward edge 16 / 16
(not full) empty backward edge
backward edge
(not empty) 33
6.4 M AXIMUM F LOW
‣ introduction
Algorithms

Start with 0 flow.

While there exists an augmenting path:
- find an augmenting path
- compute bottleneck capacity
- increase flow on that path by bottleneck capacity
Questions.
・How to compute a mincut? Easy. ✔
・How to find an augmenting path? BFS works well.
・If FF terminates, does it always compute a maxflow? Yes. ✔
・Does FF always terminate? If so, after how many augmentations?
yes, provided edge capacities are integers requires clever analysis
(or augmenting paths are chosen carefully)
35
Ford-Fulkerson algorithm with integer capacities
Important special case. Edge capacities are integers between 1 and U.
flow on each edge is an integer
Invariant. The flow is integer-valued throughout Ford-Fulkerson.

Pf. [by induction]
・Bottleneck capacity is an integer.
・Flow on an edge increases/decreases by bottleneck capacity.
Proposition. Number of augmentations ≤ the value of the maxflow.
Pf. Each augmentation increases the value by at least 1.
critical for some applications (stay tuned)
Integrality theorem. There exists an integer-valued maxflow.

Pf. Ford-Fulkerson terminates and maxflow that it finds is integer-valued.
36
Bad case for Ford-Fulkerson
Bad news. Even when edge capacities are integers, number of augmenting
paths could be equal to the value of the maxflow.
initialize with 0 flow s
flow
0
0
0
10
10
capacity
0
0
1
0
0
10
0
10
0
t
37
1st iteration s
1
0
0
0
10
10
0
0 1
1
1
0
0
10
0
10
0
t
38
2nd iteration s
0
0
10
10
1
0
1 0
1
0
1
10
0
1
10
0
t
39
3rd iteration s
2
1
1
0
10
10
0
0 1
1
2
1
1
10
0
10
0
t
40
4th iteration s
1
0
10
10
2
0
1 0
1
1
2
10
0
2
10
0
t
41
...
42
199th iteration s
0
10
99
99 0
0
10
10
0 1
1
0
10
99
99 0
10
0
10
t
43
200th iteration s
99 0
10
0
10
10
10
0
1 0
1
10 0
99 0
10
10
0
10
0
t
44
can be exponential in input size
Good news. This case is easily avoided. [use shortest/fattest path]
10 0
10
0
0
10
10
0
1
10
10 0
10
0
10
0
0
t
45
How to choose augmenting paths?
Use care when selecting augmenting paths.

・Some choices lead to exponential algorithms.
・Clever choices lead to polynomial algorithms.
augmenting path number of paths implementation
random path ≤EU randomized queue
DFS path ≤EU stack (DFS)
shortest path ≤ ½EV queue (BFS)
fattest path ≤ E ln(E U) priority queue
digraph with V vertices, E edges, and integer capacities between 1 and U
46
How to choose augmenting paths?
Choose augmenting paths with:

・Shortest path: fewest number of edges.
・Fattest path: max bottleneck capacity.
Theoretical Improvements in Algorithmic Efficiency

for Network Flow Problems
JACK EDMONDS
University of Waterloo, Waterloo, Ontario, Canada

AND
RICHARD M. K A R P
University of California, Berkeley, California
ABSTRACT. This paper presents new algorithms for t h e m a x i m u m flow problem, the Hitchcock
t r a n s p o r t a t i o n problem, and t h e general m i n i m u m - c o s t flow problem. U p p e r bounds on the
numbers of steps in these algorithms are derived, and are shown to compale favorably with
upper bounds on t h e numbers of steps required by earlier algorithms.
First, the paper states the m a x i m u m flow problem, gives the F o r d - F u l k e r s o n labeling method
for its solution, and points out t h a t an improper choice of flow a u g m e n t i n g p a t h s can lead to
Edmonds-Karp 1972 (USA)

severe c o m p u t a t i o n a l difficulties. T h e n rules of choice t h a t avoid these difficulties are given.
We show t h a t , if each flow a u g m e n t a t i o n is made along an a u g m e n t i n g p a t h h a v i n g a minimum Dinic 1970 (Soviet Union)
n u m b e r of arcs, t h e n a m a x i m u m flow in an n-node network will be o b t a i n e d a f t e r no more t h a n
~(n a - n) a u g m e n t a t i o n s ; and t h e n we show t h a t if each flow change is chosen to produce a
m a x i m u m increase in the flow value then, provided the capacities are integral, a m a x i m u m flow
will be d e t e r m i n e d within at most 1 + logM/(M--1) if(t, S) a u g m e n t a t i o n s , wheref*(t, s) is the
value of the maximum flow and M is the m a x i m u m n u m b e r of arcs across a cut. 47
Next a new algorithm is given for the m i n i m u m - c o s t flow problem, in which all s h o r t e s t - p a t h
6.4 M AXIMUM F LOW
‣ introduction
Algorithms

Flow network representation
Flow edge data type. Associate flow fe and capacity ce with edge e = v→w.
flow fe capacity ce
v 7/9 w
Flow network data type. Must be able to process edge e = v→w in either
direction: include e in adjacency lists of both v and w.
Residual (spare) capacity.

・Forward edge: residual capacity = c – f . e e
・Backward edge: residual capacity = f . e
residual capacity
forward edge
Augment flow.
・Forward edge: add ∆ .
2
v w
・Backward edge: subtract ∆ . 7
backward edge
49
includes all edges with

Residual network. A useful view of a flow network. positive residual capacity
original network 9/9
4 9
/4 /
10
10 4/4 0 / 15
/
9
s 4/5 0/8 4 / 10 t
backward edge
residual network 9 (not empty)
9
9
4 15 1
1 4
s 1 8 6 t
4 4
forward edge
(not full)
Key point. Augmenting paths in original network are in 1-1

correspondence with directed paths in residual network.
50
Flow edge API
public class FlowEdge
FlowEdge(int v, int w, double capacity) create a flow edge v→w
int from() vertex this edge points from
int to() vertex this edge points to
int other(int v) other endpoint
double capacity() capacity of this edge
double flow() flow in this edge
double residualCapacityTo(int v) residual capacity toward v
void addResidualFlowTo(int v, double delta) add delta flow toward v
residual capacity
forward edge
flow fe capacity ce
v 7/9 w v w
7
backward edge
51
Flow edge: Java implementation
public class FlowEdge

{
private final int v, w; // from and to
private final double capacity; // capacity
private double flow; // flow flow variable
(mutable)
public FlowEdge(int v, int w, double capacity)
{
this.v = v;
this.w = w;
this.capacity = capacity;
}
public int from() { return v; }

public int to() { return w; }
public double capacity() { return capacity; }
public double flow() { return flow; }
public int other(int vertex)

{
if (vertex == v) return w;
else if (vertex == w) return v;
else throw new IllegalArgumentException();
}
public double residualCapacityTo(int vertex) {...}

public void addResidualFlowTo(int vertex, double delta) {...} next slide
}
52
Flow edge: Java implementation (continued)
public double residualCapacityTo(int vertex)

{
if (vertex == v) return flow; forward edge
else if (vertex == w) return capacity - flow; backward edge
}
public void addResidualFlowTo(int vertex, double delta)

{
if (vertex == v) flow -= delta; forward edge
else if (vertex == w) flow += delta;
backward edge
}
residual capacity
forward edge
flow fe capacity ce
v 7/9 w v w
7
backward edge
53
Flow network API
public class FlowNetwork
FlowNetwork(int V) create an empty flow network with V vertices
FlowNetwork(In in) construct flow network input stream
void addEdge(FlowEdge e) add flow edge e to this flow network
Iterable<FlowEdge> adj(int v) forward and backward edges incident to v
Iterable<FlowEdge> edges() all edges in this flow network
int V() number of vertices
int E() number of edges
String toString() string representation
Conventions. Allow self-loops and parallel edges.

54
Flow network: Java implementation
public class FlowNetwork

{
same as EdgeWeightedGraph,
private final int V;
but adjacency lists of
private Bag<FlowEdge>[] adj;
FlowEdges instead of Edges
public FlowNetwork(int V)
{
this.V = V;
adj = (Bag<FlowEdge>[]) new Bag[V];
for (int v = 0; v < V; v++)
adj[v] = new Bag<FlowEdge>();
}
public void addEdge(FlowEdge e)

{
int v = e.from();
int w = e.to();
adj[v].add(e); add forward edge
adj[w].add(e); add backward edge
}
public Iterable<FlowEdge> adj(int v)

{ return adj[v]; }
}
55
Flow network: adjacency-lists representation
Maintain vertex-indexed array of FlowEdge lists (use Bag abstraction).
tinyFN.txt references to the same

0 2 3.0 1.0 0 1 2.0 2.0 FlowEdge object
V
6 adj[]
E
8 0 1 4 1.0 0.0 1 3 3.0 2.0 0 1 2.0 2.0
0 1 2.0
1
0 2 3.0
2 2 4 1.0 1.0 2 3 1.0 0.0 0 2 3.0 1.0
1 3 3.0
1 4 1.0 3
2 3 1.0 3 5 2.0 2.0 2 3 1.0 0.0 1 3 3.0 2.0
4
2 4 1.0
3 5 2.0 5 4 5 3.0 1.0 2 4 1.0 1.0 1 4 1.0 0.0
4 5 3.0
4 5 3.0 1.0 3 5 2.0 2.0 Bag
objects
Note. Adjacency list includes edges with 0 residual capacity.

(residual network is represented implicitly)
56
Finding a shortest augmenting path (cf. breadth-first search)
private boolean hasAugmentingPath(FlowNetwork G, int s, int t)

{
edgeTo = new FlowEdge[G.V()];
marked = new boolean[G.V()];
Queue<Integer> queue = new Queue<Integer>();

queue.enqueue(s);
marked[s] = true;
while (!queue.isEmpty())
{
int v = queue.dequeue();
for (FlowEdge e : G.adj(v)) found path from s to w

{ in the residual network?
int w = e.other(v);
if (!marked[w] && (e.residualCapacityTo(w) > 0) )
{
edgeTo[w] = e; save last edge on path to w;
marked[w] = true; mark w;
queue.enqueue(w); add w to the queue
}
}
}
return marked[t]; is t reachable from s in residual network?

}
57
Ford-Fulkerson: Java implementation
public class FordFulkerson

{
private boolean[] marked; // true if s->v path in residual network
private FlowEdge[] edgeTo; // last edge on s->v path
private double value; // value of flow
public FordFulkerson(FlowNetwork G, int s, int t)

{ compute edgeTo[]
value = 0.0;
while (hasAugmentingPath(G, s, t)) compute
{ bottleneck capacity
double bottle = Double.POSITIVE_INFINITY;
for (int v = t; v != s; v = edgeTo[v].other(v))
bottle = Math.min(bottle, edgeTo[v].residualCapacityTo(v));
for (int v = t; v != s; v = edgeTo[v].other(v))

edgeTo[v].addResidualFlowTo(v, bottle);
value += bottle; augment flow

}
}
private boolean hasAugmentingPath(FlowNetwork G, int s, int t)

{ /* See previous slide. */ }
public double value()

{ return value; }
public boolean inCut(int v) is v reachable from s in residual network?

{ return marked[v]; }
}
58
6.4 M AXIMUM F LOW
‣ introduction
Algorithms

Maxflow and mincut applications
Maxflow/mincut is a widely applicable problem-solving model.
・Data mining.
・Open-pit mining.
・Bipartite matching.
・Network reliability.
・Baseball elimination.
・Image segmentation. liver and hepatic vascularization segmentation
・Network connectivity.
・Distributed computing.
・Security of statistical data.
・Egalitarian stable matching.
・Multi-camera scene reconstruction.
・Sensor placement for homeland security.
・Many, many, more.
60
Bipartite matching problem
N students apply for N jobs.
bipartite matching problem
Each gets several offers. 1 Alice 6 Adobe

Adobe Alice
Amazon Bob
Google Carol
2 Bob 7 Amazon
Adobe Alice
Amazon Bob
3 Carol Dave
Adobe Eliza
Facebook 8 Facebook
Google Carol
Is there a way to match all students to jobs?
4 Dave 9 Google
Amazon Alice
Yahoo Carol
5 Eliza 10 Yahoo
Amazon Dave
Yahoo Eliza
61
Bipartite matching problem
Given a bipartite graph, find a perfect matching.
perfect matching (solution) bipartite graph bipartite matching problem
1 6 1 Alice 6 Adobe
Alice —— Google
Adobe Alice
Bob —— Adobe Amazon Bob
Google Carol
Carol —— Facebook 2 7
2 Bob 7 Amazon
Dave —— Yahoo Adobe Alice
Eliza —— Amazon 3 8
Amazon Bob
3 Carol Dave
Adobe Eliza
Facebook 8 Facebook
4 9
Google Carol
4 Dave 9 Google
Amazon Alice
5 10
Yahoo Carol
5 Eliza 10 Yahoo
N students N companies
Amazon Dave
Yahoo Eliza
62
Network flow formulation of bipartite matching
・Create s, t, one vertex for each student, and one vertex for each job.
・Add edge from s to each student (capacity 1).
・Add edge from each job to t (capacity 1).
・Add edge from student to each job offered (infinite capacity).
flow network bipartite matching problem
1 6 1 Alice 6 Adobe
Adobe Alice
Amazon Bob
2 7 Google Carol
2 Bob 7 Amazon
Adobe Alice
s 3 8 t Amazon Bob
3 Carol Dave
Adobe Eliza
Facebook 8 Facebook
4 9
Google Carol
4 Dave 9 Google
Amazon Alice
5 10
Yahoo Carol
5 Eliza 10 Yahoo
Amazon Dave
Yahoo Eliza
63
Network flow formulation of bipartite matching
1-1 correspondence between perfect matchings in bipartite graph and

integer-valued maxflows of value N.
flow network bipartite matching problem
1 6 1 Alice 6 Adobe
Adobe Alice
Amazon Bob
2 7 Google Carol
2 Bob 7 Amazon
Adobe Alice
s 3 8 t Amazon Bob
3 Carol Dave
Adobe Eliza
Facebook 8 Facebook
4 9
Google Carol
4 Dave 9 Google
Amazon Alice
5 10
Yahoo Carol
5 Eliza 10 Yahoo
Amazon Dave
Yahoo Eliza
64
What the mincut tells us
Goal. When no perfect matching, explain why.
1 6
S = { 2, 4, 5 }
2 7 T = { 7, 10 }
student in S
3 8
can be matched
only to
companies in T
4 9
|S| > | T |
5 10
no perfect matching exists
65
What the mincut tells us
Mincut. Consider mincut (A, B).

・Let S = students on s side of cut.
・Let T = companies on s side of cut.
・Fact: | S | > | T |; students in S can be matched only to companies in T.
1 6
S = { 2, 4, 5 }
2 7 T = { 7, 10 }
student in S
s 3 8 t
can be matched
only to
companies in T
4 9
|S| > | T |
5 10
no perfect matching exists
Bottom line. When no perfect matching, mincut explains why.

66
Baseball elimination problem
Q. Which teams have a chance of finishing the season with the most wins?
i team wins losses to play ATL PHI NYM MON
0 Atlanta 83 71 8 – 1 6 1
1 Philly 80 79 3 1 – 0 2
2 New York 78 78 6 6 0 – 0
3 Montreal 77 82 3 1 2 0 –
Montreal is mathematically eliminated.

・Montreal finishes with ≤ 80 wins.
・Atlanta already has 83 wins.
67
i team wins losses to play ATL PHI NYM MON
0 Atlanta 83 71 8 – 1 6 1
1 Philly 80 79 3 1 – 0 2
2 New York 78 78 6 6 0 – 0
3 Montreal 77 82 3 1 2 0 –
Philadelphia is mathematically eliminated.

・Philadelphia finishes with ≤ 83 wins.
・Either New York or Atlanta will finish with ≥ 84 wins.
Observation. Answer depends not only on how many games already won
and left to play, but on whom they're against.
68
i team wins losses to play NYY BAL BOS TOR DET
0 New York 75 59 28 – 3 8 7 3
1 Baltimore 71 63 28 3 – 2 7 4
2 Boston 69 66 27 8 2 – 0 0
3 Toronto 63 72 27 7 7 0 – 0
4 Detroit 49 86 27 3 4 0 0 –
AL East (August 30, 1996)
Detroit is mathematically eliminated.

・Detroit finishes with ≤ 76 wins.
・Wins for R = { NYY, BAL, BOS, TOR } = 278.
・Remaining games among { NYY, BAL, BOS, TOR } = 3 + 8 + 7 + 2 + 7 = 27.
・Average team in R wins 305/4 = 76.25 games.
69
Baseball elimination problem: maxflow formulation
Intuition. Remaining games flow from s to t.
0–1
games left team 2 can still win

between 1 and 2 0–2 0 this many more games
0–3 1
∞
s g12 1–2 ∞ 2 w4 + r4 – w2 t
1–3 3
team vertices
2–3 (each team other than 4)
game vertices
(each pair of teams other than 4)
Fact. Team 4 not eliminated iff all edges pointing from s are full in maxflow.
70
Maximum flow algorithms: theory
(Yet another) holy grail for theoretical computer scientists.
year method worst case discovered by
1951 simplex E3 U Dantzig
1955 augmenting path E2 U Ford-Fulkerson
1970 shortest augmenting path E3 Dinitz, Edmonds-Karp
1970 fattest augmenting path E2 log E log( E U ) Dinitz, Edmonds-Karp
1977 blocking flow E 5/2 Cherkasky
1978 blocking flow E 7/3 Galil
1983 dynamic trees E2 log E Sleator-Tarjan
1985 capacity scaling E2 log U Gabow
1997 length function E3/2 log E log U Goldberg-Rao
2012 compact network E2 / log E Orlin
? ? E ?
maxflow algorithms for sparse digraphs with E edges, integer capacities between 1 and U
71
Maximum flow algorithms: practice
Warning. Worst-case order-of-growth is generally not useful for predicting

or comparing maxflow algorithm performance in practice.
Best in practice. Push-relabel method with gap relabeling: E 3/2.
On I m p l e m e n t i n g P u s h - R e l a b e l M e t h o d
for the M a x i m u m Flow P r o b l e m
EUROPEAN
JOURNAL
OF OPERATIONAL
Boris V. Cherkassky 1 and Andrew V. Goldberg 2 RESEARCH
ELSEVIER European Journal of Operational Research 97 (1997) 509-542
1 Central Institute for Economics and Mathematics,
Krasikova St. 32, 117418, Moscow, Russia
[email protected]
2 Computer Science Department, Stanford University Theory and Methodology
Stanford, CA 94305, USA
goldberg~cs. stanford, edu Computational investigations of maximum flow algorithms
Ravindra K . A h u j a a, M u r a l i K o d i a l a m b, A j a y K . M i s h r a c, J a m e s B . O r l i n d,.
A b s t r a c t . We study efficient implementations of the push-relabel method a Department t~'lndustrial and Management Engineering. Indian Institute of Technology. Kanpur, 208 016, India
for the maximum flow problem. The resulting codes are faster than the b AT& T Bell Laboratories, Holmdel, NJ 07733, USA
c KA'F-ZGraduate School of Business, University of Pittsburgh, Pittsburgh, PA 15260, USA
previous codes, and much faster on some problem families. The speedup d Sloun School of Management, Massachusetts Institute of Technology. Cambridge. MA 02139. USA
is due to the combination of heuristics used in our implementations. We
also exhibit a family of problems for which the running time of all known Received 30 August 1995; accepted 27 June 1996
methods seem to have a roughly quadratic growth rate.
Abstract
1 Introduction The maximum flow algorithm is distinguished by the long line of successive contributions researchers have made in
obtaining algorithms with incrementally better worst-case complexity. Some, but not all, of these theoretical improvements
The rnaximum flow problem is a classical combinatorial problem that comes up have produced improvements in practice. The purpose of this paper is to test some of the major algorithmic ideas developed
in a wide variety of applications. In this paper we study implementations of the in the recent years and to assess their utility on the empirical front. However, our study differs from previous studies in
push-rdabel [13, 17] method for the problem. several ways. Whereas previous studies focus primarily on CPU time analysis, our analysis goes further and provides 72
detailed insight into algorithmic behavior. It not only observes how algorithms behave but also tries to explain why
Summary
Mincut problem. Find an st-cut of minimum capacity.

Maxflow problem. Find an st-flow of maximum value.
Duality. Value of the maxflow = capacity of mincut.
Proven successful approaches.

・Ford-Fulkerson (various augmenting-path strategies).
・Preflow-push (various versions).
Open research challenges.
・Practice: solve real-world maxflow/mincut problems in linear time.
・Theory: prove it for worst-case inputs.
・Still much to be learned!
73

64 Max Flow

Uploaded by

Copyright:

Available Formats

64 Max Flow

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

64 Max Flow

Uploaded by

Copyright:

Available Formats

Algorithms R OBERT S EDGEWICK | K EVIN W AYNE

6.4 M AXIMUM F LOW

R OBERT S EDGEWICK | K EVIN W AYNE

R OBERT S EDGEWICK | K EVIN W AYNE

Input. An edge-weighted digraph, source vertex s, and target vertex t.

each edge has a

don't count edges

Minimum st-cut (mincut) problem. Find a cut of minimum capacity.

rail network connecting Soviet Union with Eastern European countries

Government-in-power’s goal. Cut off communication to set of people.

Input. An edge-weighted digraph, source vertex s, and target vertex t.

each edge has a

Def. An st-flow (flow) is an assignment of values to the edges such that:

Def. An st-flow (flow) is an assignment of values to the edges such that:

we assume no edges point to s or from t

s 5/5 5/8 10 / 10 t value = 5 + 10 + 10 = 25

Def. An st-flow (flow) is an assignment of values to the edges such that:

Maximum st-flow (maxflow) problem. Find a flow of maximum value.

s 5/5 8/8 10 / 10 t value = 8 + 10 + 10 = 28

Soviet Union goal. Maximize flow of supplies to Eastern Europe.

rail network connecting Soviet Union with Eastern European countries

"Free world" goal. Maximize flow of information to specified set of people.

Input. A weighted digraph, source vertex s, and target vertex t.

value of flow = 28 capacity of cut = 28

Remarkable fact. These two problems are dual!

R OBERT S EDGEWICK | K EVIN W AYNE

Initialization. Start with 0 flow.

Augmenting path. Find an undirected path from s to t such that:

Augmenting path. Find an undirected path from s to t such that:

Augmenting path. Find an undirected path from s to t such that:

Augmenting path. Find an undirected path from s to t such that:

Termination. All paths from s to t are blocked by either a

full forward edge

Start with 0 flow.

R OBERT S EDGEWICK | K EVIN W AYNE

net flow across cut = 5 + 10 + 10 = 25

s 5/5 5/8 10 / 10 t value of flow = 25

net flow across cut = 10 + 5 + 10 = 25

s 5/5 5/8 10 / 10 t value of flow = 25

net flow across cut = (10 + 10 + 5 + 10 + 0 + 0) – (5 + 5 + 0 + 0) = 25

s 5/5 5/8 10 / 10 t value of flow = 25

Intuition. Conservation of flow.

Pf. By induction on the size of B.

Corollary. Outflow from s = inflow to t = value of flow.

flow-value lemma flow bounded by capacity

value of flow = 27 capacity of cut = 30

Augmenting path theorem. A flow f is a maxflow iff no augmenting paths.

Augmenting path theorem. A flow f is a maxflow iff no augmenting paths.

[ ii iii ] We prove contrapositive: ~iii ~ii.

Augmenting path theorem. A flow f is a maxflow iff no augmenting paths.

= value of flow f. flow-value lemma

To compute mincut (A, B) from maxflow f :

full forward edge

R OBERT S EDGEWICK | K EVIN W AYNE

Start with 0 flow.

Important special case. Edge capacities are integers between 1 and U.

flow on each edge is an integer

Invariant. The flow is integer-valued throughout Ford-Fulkerson.

critical for some applications (stay tuned)