Network flow problems

Network flow problems

-

Introduction of: network, max-flow problem capacity, flow Ford-Fulkerson method pseudo code, residual networks, augmenting paths cuts of networks max-flow min-cut theorem example of an execution analysis, running time, variations of the max-flow problem

Introduction network
Practical examples of a network - liquids flowing through pipes - parts through assembly lines - current through electrical network - information through communication network - goods transported on the road

Introduction - network
Representation
Flow network: directed graph G=(V,E)
v1 v3 v1 v3

Example: oil pipeline

v2

v4

source

v2

v4

sink

Introduction max-flow problem

Representation
Flow network: directed graph G=(V,E)
v1 v3 v1 v3

Example: oil pipeline

v2

v4

source

v2

v4

sink

Informal definition of the max-flow problem: What is the greatest rate at which material can be shipped from the source to the sink without violating any capacity contraints?

Introduction - capacity
Representation
Flow network: directed graph G=(V,E)
3 v1 8 S 3 6 v2 6 12 v4 8 3 v3 6 S v1 v3

Example: oil pipeline

v2

v4

c(u,v)=12
u 6 v

Big pipe

c(u,v)=6

Small pipe

Introduction - capacity
Representation
Flow network: directed graph G=(V,E)
3 v1 8 S 3 6 v2 6 v4 8 3 v3 6 S v1 v3

Example: oil pipeline

v2

v4

If (u,v) E c(u,v) = 0
6 v2 0 0 v4 0 v3 v4

Introduction flow
Representation
Flow network: directed graph G=(V,E)
3 v1 8 S 3 6 v2 6 6/12 v4 8 3 v3 6 S v1 v3

Example: oil pipeline

v2

v4

f(u,v)=6
u 6/6 v

Flow below capacity

f(u,v)=6

Maximum flow

Introduction flow
Representation
Flow network: directed graph G=(V,E)
3 v1 8 S 3 6 v2 6 v4 8 3 v3 6 S v1 v3

Example: oil pipeline

v2

v4

Introduction flow
Representation
Flow network: directed graph G=(V,E)
3 v1 8 S 3 6/6 v2 6/6 v4 6/8 3 v3 6 S v1 v3

Example: oil pipeline

v2

v4

Introduction flow
Representation
Flow network: directed graph G=(V,E)
3 v1 8 S 3 6/6 v2 6/6 v4 6/8 3 v3 6 S v1 v3

Example: oil pipeline

v2

v4

Introduction flow
Representation
Flow network: directed graph G=(V,E)
3/3 v1 3/8 S 3 6/6 v2 6/6 v4 6/8 3 v3 3/6 S v1 v3

Example: oil pipeline

v2

v4

Introduction flow
Representation
Flow network: directed graph G=(V,E)
3/3 v1 3/8 S 3 6/6 v2 6/6 v4 6/8 3 v3 3/6 S v1 v3

Example: oil pipeline

v2

v4

Introduction flow
Representation
Flow network: directed graph G=(V,E)
3/3 v1 5/8 S 3 6/6 v2 6/6 v4 8/8 2/3 v3 3/6 S v1 v3

Example: oil pipeline

v2

v4

Introduction cancellation
Representation
Flow network: directed graph G=(V,E)
3/3 v1 5/8 S 3 6/6 v2 6/6 v4 8/8 2/3 v3 3/6 S v1 v3

Example: oil pipeline

v2

v4

Introduction cancellation
Representation
Flow network: directed graph G=(V,E)
3/3 v1 6/8 S 1/3 6/6 v2 5/6 v4 8/8 3/3 v3 4/6 S v1 v3

Example: oil pipeline

v2

v4

u 10 4 8/10

u 4 8/10

u 3/4 5/10

u 4

Flow properties
Flow in G = (V,E): f: V x V R with 3 properties: 1) Capacity constraint: For all u,v V : f(u,v) < c(u,v) 2) Skew symmetry: For all u,v V : f(u,v) = - f(v,u)
vV

3) Flow conservation: For all u V \ {s,t} :

f(u,v) = 0

Flow properties
Flow in G = (V,E): f: V x V R with 3 properties: 1) Capacity constraint: For all u,v V : f(u,v) < c(u,v) 2) Skew symmetry: For all u,v V : f(u,v) = - f(v,u)
vV

3) Flow conservation: For all u V \ {s,t} :

Flow network G = (V,E)
16 11/

f(u,v) = 0

v1

12/12

v3

15 /20
t

Note: by skew symmetry f (v3,v1) = - 12

1/4

4/9

7/7

10

8/1

v2

11/14

v4

4/4

Net flow and value of a flow

u 8/10 3/4 5/10 u 4

f(u,v) = 5 f(v,u) = -5

v 3/3 v1 6/8 S 1/3 6/6 v2 5/6 3/3

v3

4/6

t 8/8

v4

The max-flow problem

Informal definition of the max-flow problem: What is the greatest rate at which material can be shipped from the source to the sink without violating any capacity contraints?

Formal definition of the max-flow problem: The max-flow problem is to find a valid flow for a given weighted directed graph G, that has the maximum value over all valid flows.

The Ford-Fulkerson method

a way how to find the max-flow

This method contains 3 important ideas: 1) residual networks 2) augmenting paths 3) cuts of flow networks

Ford-Fulkerson pseudo code

1 initialize flow f to 0 2 while there exits an augmenting path p 3 do augment flow f along p 4 return f

Ford Fulkerson residual networks

The residual network Gf of a given flow network G with a valid flow f consists of the same vertices v V as in G which are linked with residual edges (u,v) Ef that can admit more strictly positive net flow. The residual capacity cf represents the weight of each edge Ef and is the amount of additional net flow f(u,v) before exceeding the capacity c(u,v)
Flow network G = (V,E)
16 11/
S v1

residual network Gf = (V,Ef)

15 /20
t S

12/12

v3

5
5 8

v1

v3

1/4

7/7

10

11
v2 v4

4/9

8/1 3

v2

11/14

v4

4/4

cf(u,v) = c(u,v) f(u,v)

Ford Fulkerson residual networks

The residual network Gf of a given flow network G with a valid flow f consists of the same vertices v V as in G which are linked with residual edges (u,v) Ef that can admit more strictly positive net flow. The residual capacity cf represents the weight of each edge Ef and is the amount of additional net flow f(u,v) before exceeding the capacity c(u,v)
Flow network G = (V,E)
16 11/
v1

residual network Gf = (V,Ef)

15 /20
t S v1

12/12

v3

12

5
11
11

v3

5 15
t

1/4

4/9

7/7

10

8/1 3

v2

11/14

v4

4/4

v2

3 11

v4

cf(u,v) = c(u,v) f(u,v)

Ford Fulkerson augmenting paths

Definition: An augmenting path p is a simple (free of any cycle) path from s to t in the residual network Gf
Residual capacity of p

cf(p) = min{cf (u,v): (u,v) is on p}

Flow network G = (V,E)
16 11/
v1

residual network Gf = (V,Ef)

15 /20
t S v1

12/12

v3

12

5
11
11

v3

5 15
t

1/4

4/9

7/7

10

8/1 3

v2

11/14

v4

4/4

v2

3 11

v4

Ford Fulkerson augmenting paths

Definition: An augmenting path p is a simple (free of any cycle) path from s to t in the residual network Gf
Residual capacity of p

cf(p) = min{cf (u,v): (u,v) is on p}

Flow network G = (V,E)
16 11/
v1

residual network Gf = (V,Ef)

15 /20
t S v1

12/12

v3

12

5
11
11

v3

5 15
t

1/4

4/9

7/7

10

8/1 3

v2

11/14

v4

4/4

v2

3 11

v4

Augmenting path

Ford Fulkerson augmenting paths

We define a flow: fp: V x V R such as: cf(p) fp(u,v) = 0 Flow network G = (V,E)
16 11/
v1

if (u,v) is on p - cf(p) if (v,u) is on p otherwise residual network Gf = (V,Ef)

12/12

v3

15 /20
t S

5
11
11

v1

12

v3

5 15
t

1/4

4/9

7/7

10

8/1 3

v2

11/14

v4

4/4

v2

3 11

v4

Ford Fulkerson augmenting paths

We define a flow: fp: V x V R such as: cf(p) if (u,v) is on p fp(u,v) = - cf(p) if (v,u) is on p 0 otherwise

Flow network G = (V,E)

16 11/
v1

residual network Gf = (V,Ef)

15 /20
t S v1

12/12

v3

12
4/4

5
11
11

v3

4/5 -4/ 1 5
t

1/4

4/5 -4/ 8

8/1 3

v2

11/14

v4

4/4

-4 /5

4/9

7/7

10

7
v4

v2

3 11

Our virtual flow fp along the augmenting path p in Gf

Ford Fulkerson augmenting the flow

We define a flow: fp: V x V R such as: cf(p) if (u,v) is on p fp(u,v) = - cf(p) if (v,u) is on p 0 otherwise

Flow network G = (V,E)

16 11/
v1

residual network Gf = (V,Ef)

19
v1

12/12

v3

12
4/4

/20
t S

5
11
11

v3

4/5 15
t

1/4

0/9

7/7

10

4/5 8

12/ 1

v2

11/14

v4

4/4

v2

3 11

v4

New flow:

f: V x V R : f=f + fp

Our virtual flow fp along the augmenting path p in Gf

Ford Fulkerson new valid flow

proof of capacity constraint Lemma: f : V x V R : f = f + fp in G
cf(p) if (u,v) is on p fp(u,v) = - cf(p) if (v,u) is on p 0 otherwise

cf(p) = min{cf (u,v): (u,v) is on p}

Capacity constraint: cf(u,v) = c(u,v) f(u,v) For all u,v V, we require f(u,v) < c(u,v) Proof: fp (u ,v) < cf (u ,v) = c (u ,v) f (u ,v) (f + fp) (u ,v) = f (u ,v) + fp (u ,v) < c (u ,v)

Ford Fulkerson new valid flow

proof of Skew symmetry Lemma: f : V x V R : f = f + fp in G

Skew symmetry: For all u,v V, we require f(u,v) = - f(v,u) Proof: (f + fp)(u ,v) = f (u ,v) + fp (u ,v) = - f (v ,u) fp (v ,u) = - (f (v ,u) + fp (v ,u)) = - (f + fp) (v ,u)

Ford Fulkerson new valid flow

proof of flow conservation Lemma: f : V x V R : f = f + fp Flow conservation: For all u V \ {s,t} : in G

f(u,v) = 0
v V

Proof: u V {s ,t} (f + fp) (u ,v) = (f(u ,v) + fp (u ,v)) vV vV = f (u ,v) + fp (u ,v) = 0 + 0 = 0

v V v V

Ford Fulkerson new valid flow

Lemma: | (f + fp) | = | f | + | fp | Value of a Flow f: Def: |f| = vV f(s,v) Proof: | (f + fp) | = (f + fp) (s ,v) = (f (s ,v) + fp (s ,v)) = f (s ,v) + fp (s ,v) = | f | + | fp |
v V v V v V vV

Ford Fulkerson new valid flow

Lemma: f : V x V R : f = f + fp | (f + fp) | = | f | + | fp | > | f | Lemma shows: if an augmenting path can be found then the above flow augmentation will result in a flow improvement. Question: If we cannot find any more an augmenting path is our flow then maximum? Idea: The flow in G is maximum the residual Gf contains no augmenting path. in G

Ford Fulkerson cuts of flow networks

New notion: cut (S,T) of a flow network A cut (S,T) of a flow network G=(V,E) is a partiton of V into S and T = V \ S such that s S and t T. Practical example
11/ 16
v1

1/4

0/9

7/7

12/ 12

v3

10

19 20 /
4/4

12/ 13

In the example: S = {s,v1,v2) , T = {v3,v4,t} Net flow f(S ,T) = f(v1,v3) + f(v2,v4) + f(v2,v3) = 12 + 11 + (-0) = 23 Capacity c(S,T) = c(v1,v3) + c(v2,v4) = 12 + 14 = 26

v2

11/ S14 T

v4

Implicit summation notation: f (S, T) =

uS

vT

f (u, v)

Ford Fulkerson cuts of flow networks

Lemma: the value of a flow in a network is the net flow across any cut of the network f (S ,T) = | f |
12/12
v3

1
S

6 1/1

v1

19 /20
t

1/4

0/9

7/7
v4

10

12/ 1

v2

4/4

11/14

proof

Ford Fulkerson cuts of flow networks

Assumption: The value of any flow f in a flow network G is bounded from above by the capacity of any cut of G Lemma: | f | < c (S, T) | f | = f (S, T) = f (u, v) S <u vT c (u, v) (S, T =u c S v T)
v1

16 11/
S

12/12

v3

19 /20
t

1/4

0/9

7/7
v4

10

12/ 1

v2

4/4

11/14

F. Fulkerson: Max-flow min-cut theorem

If f is a flow in a flow network G = (V,E) with source s and sink t, then the following conditions are equivalent: 1. f is a maximum flow in G. 2. The residual network Gf contains no augmenting paths. 3. | f | = c (S, T) for some cut (S, T) of G.
proof:
(1)

(2):

We assume for the sake of contradiction that f is a maximum flow in G but that there still exists an augmenting path p in Gf. Then as we know from above, we can augment the flow in G according to the formula: f= f + fp. That would create a flow fthat is strictly greater than the former flow f which is in contradiction to our assumption that f is a maximum flow.

F. Fulkerson: Max-flow min-cut theorem

If f is a flow in a flow network G = (V,E) with source s and sink t, then the following conditions are equivalent: 1. f is a maximum flow in G. 2. The residual network Gf contains no augmenting paths. 3. | f | = c (S, T) for some cut (S, T) of G.
proof: (2) (3):
v1 6/8 S 1/3 6/6 v2 5/6 v4 8/8 3/3

original flow network G

3/3 v3 4/6

residual network Gf
3 v1 2 6 t S 2 6 v2 1 5 v4 8 3 1 4 t v3 2

F. Fulkerson: Max-flow min-cut theorem

If f is a flow in a flow network G = (V,E) with source s and sink t, then the following conditions are equivalent: 1. f is a maximum flow in G. 2. The residual network Gf contains no augmenting paths. 3. | f | = c (S, T) for some cut (S, T) of G.
proof: (2) (3): Define S = {v V | path p from s to v in Gf } T = V \ S (note t S according to (2))
v1 2 6 S 2 6 v2 1 5 v4 8 3 1 4 t

residual network Gf
3 v3 2

F. Fulkerson: Max-flow min-cut theorem

If f is a flow in a flow network G = (V,E) with source s and sink t, then the following conditions are equivalent: 1. f is a maximum flow in G. 2. The residual network Gf contains no augmenting paths. 3. | f | = c (S, T) for some cut (S, T) of G.
proof: (2) (3): Define S = {v V | path p from s to v in Gf } T = V \ S (note t S according to (2))

original network G
3/3 v1 6/8 S 1/3 6/6 v2 1 5/6 v4 8/8 3/3 v3 4/6

for u S, v T: f (u, v) = c (u, v) (otherwise (u, v) Ef and v S) | f | = f (S, T) = c (S, T)

F. Fulkerson: Max-flow min-cut theorem

If f is a fow in a flow network G = (V,E) with source s and sink t, then the following conditions are equivalent: 1. f is a maximum flow in G. 2. The residual network Gf contains no augmenting paths. 3. | f | = c (S, T) for some cut (S, T) of G.
proof: (3) (1): as proofed before | f | = f (S, T) < c (S, T) the statement of (3) : | f | = c (S, T) implies that f is a maximum flow

The basic Ford Fulkerson algorithm

1 for each edge (u, v) E [G] do f [u, v] = 0 2 3 f [v, u] = 0 4 while there exists a path p from s to t in the residual network Gf do cf (p) = min {cf (u, v) | (u, v) is in p} 5 for each edge (u, v) in p 6 do f [u, v] = f [u, v] + cf (p) 7 8 f [v, u] = - f [u, v]

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4 5 6 7 8
(residual) network Gf
v1

12

v3

16
S

20
t

13

v2

14

v4

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

10

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
6 0 /1
v1

0/12

v3

0/2 0

0/9

0/1

v2

0/14

v4

0/4

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

0/10

0/4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

16
S

20

13

v2

14

v4

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

10

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

16
S

20

13

v2

14

v4

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]
temporary variable: cf (p) = 12

10

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

16
S

20

13

v2

14

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]
temporary variable:

10

12/12

9
v3

12 /20
t

10

13

cf (p) = 12

v2

14

v4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12

13

v2

14

v4

new flow network G

16 12/
S v1

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

12 /20
t

10

13

v2

14

v4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12

13

v2

14

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

12 /20
t

10

13

v2

14

v4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12

13

v2

14

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

12 /20
t

10

13

v2

14

v4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12

13

v2

14

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

12 /20
t

10

temporary variable: cf (p) = 4

13

v2

14

v4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12

13

v2

14

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]
temporary variable:

12/12

9
v3

12 /20
t

10

cf (p) = 4

4/1 3

v2

4/14

v4

4/4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12
4 9

4
v2

10

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

12 /20
t

10

4/1 3

v2

4/14

v4

4/4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12
4 9

4
v2

10

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

12 /20
t

10

4/1 3

v2

4/14

v4

4/4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12
4 9

4
v2

10

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

12 /20
t

10

4/1 3

v2

4/14

v4

4/4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12
4 9

4
v2

10

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]
temporary variable:

12/12

9
v3

12 /20
t

10

cf (p) = 7

4/1 3

v2

4/14

v4

4/4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

8 12

10

12
4 9

4
v2

10

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]
temporary variable:

12/12

9
v3

19 /20
t

7/7

10

cf (p) = 7

11/ 1

v2

11/14

v4

4/4

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

1 19

10

12
11 2

11
v2

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

19 /20
t

7/7
v4

10

11/ 1

v2

4/4

11/14

The basic Ford Fulkerson algorithm

example of an execution
1 2 3 4
t

(residual) network Gf
v1

12

v3

4
S

1 19

10

12
11 2

11
v2

v4

new flow network G v1

16 12/
S

5 6 7 8

for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

12/12

9
v3

19 /20
t

7/7

10

Finally we have: | f | = f (s, V) = 23

4
9

11/ 1

v2

11/14

v4

4/4

Analysis of the Ford Fulkerson algorithm

Running time
1 2 3 4 5 6 7 8 for each edge (u, v) E [G] do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]

The running time depends on how the augmenting path p in line 4 is determined.

Analysis of the Ford Fulkerson algorithm

Running time (arbitrary choice of p)
1 2 3 4 5 6 7 8 for each edge (u, v) E [G] O(|E|) do f [u, v] = 0 f [v, u] = 0 while there exists a path p from s to t O(|E|) in the residual network Gf do cf(p) = min{cf(u, v) | (u, v) p} for each edge (u, v) in p O(|E|) do f [u, v] = f [u, v] + cf(p) f [v, u] = - f [u, v]
running time: O ( |E| | fmax| ) with fmax as maximum (1) The augmenting pathflow is chosen arbitrarily and all capacities are integers

O(|E| | fmax|)

Analysis of the Ford Fulkerson algorithm

Running time (arbitrary choice of p)
Consequencies of an arbitrarily choice: Example if |f*| is large:
1 ,0 00 00, 0
1,0

v1

00

,00

s
1, 0 0 0, 00 0

t
00 0,0 0

1
v2
1,0

running time: O ( |E| | fmax| ) with fmax as maximum (1) The augmenting flow is chosen arbitrarily and all capacities are integers path

Analysis of the Ford Fulkerson algorithm

Running time (arbitrary choice of p)
Consequencies of an arbitrarily choice: Example if |f*| is large:
1 / 1, ,0 000 00
1,0

residual network Gf
99 9 ,9 1

v1

00

, 00

99

v1

1,0

00 , 00

s
1, 0 00 , 000

1/1

t
0 1,0 0 0,0 0

s
1,0 00 , 000

t
1 9 9,9 9

1
v2
99

v2

1/

running time: O ( |E| | fmax| ) with fmax as maximum (1) The augmenting flow is chosen arbitrarily and all capacities are integers path

Analysis of the Ford Fulkerson algorithm

Running time (arbitrary choice of p)
Consequencies of an arbitrarily choice: Example if |f*| is large:
1/ 1 ,0 00 0,0 0
1/

residual network Gf
,9 999 99 1

v1

1,0

00

,00

v1

99 1

9, 9 99

s
1/ 1,0 00 , 0 00

t
0 1,0 0 0 ,00

s
99 9 1 ,99 9

t
1 9 9,9 9

1
v2
99

v2

1/

running time: O ( |E| | fmax| ) with fmax as maximum (1) The augmenting flow is chosen arbitrarily and all capacities are integers path

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Informal idea of the proof:

(1)

for all vertices v V\{s,t}: the shortest path distance f(s,v) in Gf increases monotonically with each flow augmentation f (s,v) < f (s,v)
S

u1

4
2

v3

6
t

u2

v4

running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Informal idea of the proof:

(1)

for all vertices v V\{s,t}: the shortest path distance f(s,v) in Gf increases monotonically with each flow augmentation . f(s,v) < f(s,v)
S

u1

4
2

v3

6
t

u2

v4

f(s,u2) = 1
running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Informal idea of the proof:

(1)

Two flow augmentations later

4
S u1

for all vertices v V\{s,t}: the shortest path distance f(s,v) in Gf increases monotonically with each flow augmentation . f(s,v) < f(s,v)

4
2

v3

4 2
t

u2

v4

f(s,u2) = 3
running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

The total number of flow augmentations performed by the algorithm is at most O(|V| |E|)
S

u1

4
2

v3

6
t

u2

v4

running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Def: critical edge (u,v) if cf(p) = cf(u,v) At least one edge on p must be critical. How many times can (u,v) be critical during an execution of Edmonds-Karp algorithm?
S u1

4
2

v3

6
t

u2

v4

Critical edges on the path p running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Idea: (u,v) can become critical at most O(V) times (After beeing critical it dissappears in Gf and can only reappear after net flow is decreased)
S u1

4
2

v3

6
t

u2

v4

our example: edge (u2,v4) running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Idea: (u,v) can become critical at most O(V) times (After beeing critical it dissappears in Gf and can only reappear after net flow is decreased)
S

Two flow augmentations later

4
u1

4
2

v3

4 2
t

u2

v4

our example: edge (u2,v4) has disappeared

running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Idea: (u,v) can become critical at most O(V) times (After beeing critical it disappears in Gf and can only reappear after net flow is decreased)
S

After the third flow augmentation

6
u1

4
2

v3

u2

2 2

v4

our example: edge (u2,v4) reappeared but is now unreachable from s running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Analysis of the Ford Fulkerson algorithm

Running time with Edmonds-Karp algorithm

Idea: (u,v) can become critical at most O(|V|) times O(|E|) pairs of vertices exist in Gf All critical edges in O(|V| |E|) O(|E|) for breath first search for p total running time O(|V| |E|) running time: O ( |V| |E| ) (2) Edmonds-Karp algorithm augmenting path is found by breath-first search and has to be a shortest path from p to t

Different variants of the max-flow problem

The algorithm of Dinic (different implementations reaps better running times than Edmonds-Karp): e.g. simultanous saturation of augmenting paths of the same length O(|V| |E|) A second capacity function lim for a lower limit of the flow function f with lim(u,v) < f(u,v) < c(u,v) A cost function cost where each edge (u,v) has got a second weight cost(u,v) and the min-cost max-flow problem Networks with multiple sources and sinks
-

Networks with multiple sources and sinks

s1

8
s2 t1

supersource

supersink

8 8
s3 t2

8
s4

Ford Fulkerson cuts of flow networks

Assumption: the value of a flow in a network is the net flow across any cut of the network Lemma: f (S ,T) = | f | Proof: f (S, T) = f (S, V\S) = f (S, V) f (S, S) = f (S, V) = f (s [S\s], V) = f (s, V) + f (S\s, V) = f (s, V) = | f |
Working with flows: X,Y,Z V and X Y = f (X, Y) =

f (x, y)

x f (X, X) = X y Y 0

f (X, Y) = - f (Y, X) f (u, V) = 0 for all u V \ {s, t} f (X Y, Z) = f (X, Z) + f (Y, Z) f (Z, X Y) = f (Z, X) + f (Z, Y)