11/10/20

Network Flow

Flow network
• Abstraction for material flowing through the edges.
• E.g. traffic on highway, pipes carrying liquid, computer networks
• ! = ($, &), directed graph.
• Two distinguished nodes: (: source, ): sink.
• *(+): capacity of edge e. *(+) ≥ 0.
2 9 5
Source Sink absorbs
generates flow 10 15 15 flow and has
4 10
and has no no outgoing
incoming edges edges
source s 5 3 8 6 10 t sink

4 6 15 10
capacity 15

4 30 7

1
 11/10/20

Flows
Def. An ! − # $%&' is a function that satisfies:
• For each ( ∈ *: 0 ≤ f (e) ≤ c(e) (capacity)
• For each , ∈ -– {!, #}: ∑ f (e) = ∑ f (e)
e in to v e out of v
(conservation)
€ v( f ) = ∑ f (e) .
Def. The value of a flow
€
$ is: e out of s
0
2 9 5
4 0 0
10€ 15 15 0 10
44
0 4 4
s 5 3 8 6 10 t

0 0
40 6 15 0 10
capacity 15
flow 0 0 Value = 4
4 30 7

Flows
?
2 9 5

10 0 6
10 44 15 15 0 10

3 8 8
s 5 3 8 6 10 t

1 ?
capacity 40 6 15 0 10
15
flow 11 11 Value = ?
4 30 7

2
 11/10/20

Maximum Flow Problem

Max flow problem: Find ! − # flow function of maximum value.

9
2 9 5
10 1 9
10 15 15 0 10
4 0
4 8 9
s 5 3 8 6 10 t

4 10
capacity 40 6 15 0 10
15
flow 14 14 Value = 28
4 30 7

Ford-Fulkerson Algorithm
Basic Algorithm:
• Identify an ! − # path and augment the flow along that path
• How to find a path? BFS or DFS
• Bottleneck along path determines amount flow can be augmented

Ford-Fulkerson ( G=(V,E), c, s, t )
1. Initialize flow f to 0 Consider an augmenting path is a
2. While exists augmenting path p do path that you can still increase the
3. Augment flow f along p flow of it. So at each edge has
4. Return f $(&) < )(&).

3
 11/10/20

Residual Graph
Original edge: ! = ($, &) ∈ ). capacity
• Flow +(!), capacity ,(!). u 17 v
Residual edge 6
• "Undo" flow sent. flow

• ! = ($, &) and !- = (&, $).

• Residual capacity: #% c(e) − f (e) if e ∈ E residual capacity
c f (e) = $ R
%& f (e ) if e R ∈ E u 11 v

Residual graph: .+ = (/, )+ ). 6

residual capacity
• Residual edges with positive residual capacity.
• )+ = {! ∶ +(!) < ,(!)} ∪ {!- ∶ +(!) > 0}.

Ford-Fulkerson Algorithm
Complete Algorithm: Ford-Fulkerson ( G=(V,E), c, s, t )

• Compute residual 1. For every edge e let f(e)=0

graph including both 2. Construct the residual graph Gf
3. While exists s-t path in Gf do
forward and 4. Let p be an s-t path in Gf
backward edges 5. Let d=mine in p cf(e)
6. For every e on p do
Def: Any ! − # path in the residual 7. If e is a forward edge then
graph is called an augmenting path. 8. f(e)+=d
9. else
Line 3 is finding an augmenting path. 10. f(reverse(e))-=d
11. Update Gf (construct new Gf)
12.Return f

4
 11/10/20

Analysis of Ford-Fulkerson
Does it terminate?
Assumption: Flow capacities are all integer values.
Invariant: Every flow value !(#) and every residual capacity
%! (#) remains an integer throughout the algorithm.
Theorem: Let C = ∑ c(e)
e out of s

Then the algorithm terminates in at most & iterations.

Pf. Each augmentation increase value by at least 1.

Analysis of Ford-Fulkerson
What is the running time?
How much work for each iteration?
• Finding an ! − # path in the residual graph $%
• $% has at most 2' edges
• Use BFS/DFS: ((' + +) = ((') since assume $ is connected
• Augment flow along the path
• ((') to update each edge along the path (conservative)
• Update the residual graph
• ((') to update each edge (conservative)
• Total running time for Ford-Fulkerson is: (('.)
• NOTE – this is pseudo-polynomial (similar to Knapsack problem)

5
 11/10/20

Analysis of Ford-Fulkerson
Does it generate the maximum flow?

To see this we will introduce the concept of a graph cut.

Cuts
Def. A ! − # cut is a partition (%, ') of ) with ! ∈ % and # ∈ '.
Def. The capacity of a cut (%, ') is: cap( A, B) = ∑ c(e)
e out of A

2 9 5

10 € 15 15 10
4

s 5 3 8 6 10 t
A
4 6 15 10
15
Capacity = 10 + 5 + 15
4 30 7 = 30

6
 11/10/20

Cuts
Def. A ! − # cut is a partition (%, ') of ) with ! ∈ % and # ∈ '.
Def. The capacity of a cut (%, ') is: cap( A, B) = ∑ c(e)
e out of A

2 9 5

€ 15 15
4
10 10

s 5 3 8 6 10 t

A 15
4 6 10
15
Capacity = 9 + 15 + 8 + 30
4 30 7 = 62

Minimum Cut Problem

Min ! − # cut problem: Find an ! − # cut of minimum capacity.

2 9 5

10 15 15 10
4

s 5 3 8 6 10 t

4 6 15 10
A 15
Capacity = 10 + 8 + 10
4 30 7 = 28

7
 11/10/20

Flows and Cuts

Flow value lemma: Let ! be any flow, and let (#, %) be any ' − ) cut.
Then, the net flow sent across the cut is equal to the amount leaving s.
∑ f (e) − ∑ f (e) = v( f )
e out of A e in to A

6
2 9 5
€ 10 0 6
10 15 15 0 10
44
3 8 8
s 5 3 8 6 10 t
A 1 10
40 6 15 0 10
15
11 11 Value = 24
4 30 7

Flows and Cuts

Flow value lemma: Let ! be any flow, and let (#, %) be any ' − ) cut.
Then, the net flow sent across the cut is equal to the amount leaving s.
∑ f (e) − ∑ f (e) = v( f )
e out of A e in to A

6
2 9 5
€ 10 0 6
10 15 15 0 10
44
3 8 8
s 5 3 8 6 10 t
A 1 10
40 6 15 0 10
15
11 11 Value = 6 + 0 + 8 - 1 + 11
4 30 7 = 24

8
 11/10/20

Flows and Cuts

Flow value lemma: Let ! be any flow, and let (#, %) be any ' − ) cut.
Then, the net flow sent across the cut is equal to the amount leaving s.
∑ f (e) − ∑ f (e) = v( f )
e out of A e in to A
6
2 9 5
10 0 6
€ 10
44 15 15 0
10
3 8 8
s 5 3 8 6 10 t
A 1 10
40 6 15 0 10
15
11 11 Value = 10 - 4 + 8 - 0 + 10
4 30 7 = 24

Flows and Cuts

Flow value lemma: Let ! be any flow, and let (#, %) be any ' − ) cut.
Then
∑ f (e) − ∑ f (e) = v( f ) .
e out of A e in to A

Pf. € v( f ) = ∑ f (e)
e out of s

by flow conservation, all terms

% (
= ∑ ' ∑ f (e) − ∑ f (e)*
except v = s are 0 v ∈ A & e out of v e in to v )

= ∑ f (e) − ∑ f (e).
e out of A e in to A

9
 11/10/20

Flows and Cuts

Weak duality: Let ! be any flow, and let (#, %) be any ' − ) cut. Then
the value of the flow is at most the capacity of the cut.
• Let ! be any flow. Then, for any ' − ) cut (#, %) we have * ! £ +,- #, % .

Pf. v( f ) = ∑ f (e) − ∑ f (e)

e out of A e in to A
≤ ∑ f (e)
e out of A
≤ ∑ c(e)
e out of A
= cap(A, B)

Certificate of Optimality
Corollary: Let ! be any flow, and let (#, %) be any cut.
If '(!) = )*+(#, %), then ! is a max flow and (#, %) is a min cut.
Value of flow = ? 9
Cut capacity = ? 2 9 5
10 1 9
Þ 10
40 15 15 0 10
Max flow = ?
4 8 9
s 5 3 8 6 10 t
A 4 10
40 6 15 0 10
15
14 14
4 30 7

10
 11/10/20

Max-Flow Min-Cut Theorem

Max-flow min-cut theorem: [Ford-Fulkerson 1956] The value of the
max flow is equal to the value of the min cut.

The Ford-Fulkerson Algorithm generates a max flow.

To prove this we exhibit an ! − # cut (%, ') with capacity equal to the
flow generated by the algorithm.

Proof of Max-Flow Min-Cut Theorem

Proof that Ford-Fulkerson generates a maximum flow:
• Let ! be a flow with no augmenting paths.
• Let " be set of vertices reachable from # in residual graph.
• By definition of ", #Î ".
• By definition of !, &Ï ".
v( f ) = ∑ f (e) − ∑ f (e)
e out of A e in to A
= ∑ c(e) All outgoing edges from A must be used at full capacity
e out of A
All incoming edges to A must be unused
= cap(A, B)

11
 11/10/20

Choosing Good Augmenting

Paths

Choosing Good Augmenting Paths

Goal: choose augmenting paths so that:
• Can find augmenting paths efficiently.
• Few iterations.

Choose augmenting paths with: [Edmonds-Karp 1972, Dinitz

1970]
• Max bottleneck capacity. (could be expensive to determine)
• Sufficiently large bottleneck capacity.
• Fewest number of edges.

12
 11/10/20

Capacity Scaling
Intuition: Choosing path with highest bottleneck capacity increases
flow by max possible amount.
• Maintain scaling parameter D.
• Let !" (D) be the subgraph of the residual graph consisting of only
edges with capacity at least D.
4 4

110 102 110 102

s 1 t s t

122 126 122 126

Gf 2 Gf (64) 2

Capacity Scaling
• Start with D = largest power of 2 that is smaller than #, the sum of
the capacities of all edges out of s.
• Discover all $ − & paths in '( (D).
• Divide D by 2 and repeat, until finding all paths with D = 1.
4 4

110 102 110 102

s 1 t s t

122 126 122 126

2 Gf (64) 2
Gf

13
 11/10/20

Capacity Scaling: Correctness and Running

Time
Correctness
• Assuming integer constraints for flow capacities
• When D = 1 Þ #$ (D) = #$.
• Upon termination of D = 1 phase, there are no augmenting paths.

Running Time
• The scaling max-flow algorithm finds a max flow in
(() log -) augmentations. It can be implemented to run in
(()2 log -) time.
• (reducing the dependency on flow capacity to log -)

Edmonds-Karp Algorithm
General Idea: For each iteration, the shortest augmentation path is chosen.

Argument: Each time an edge is a bottleneck edge on an augmentation

path, it is temporarily removed from the residual graph. By the time it
returns to the residual graph and is again a critical edge, it must be part of a
shortest path that is at least length 2 longer than previously.

Running Time: Each edge can be a critical edge at most !/2 times, since all
shortest paths will be length ! − 1 or less. Every augmentation must
involve at least one critical edge. Thus the total number of augmentations
is &(!(), and the total running time of Edmonds-Karp is &(!(2).
Dependency on C has been completely removed.

14