5Network problems

IB Optimisation

5.4 The maximum flow problem

Suppose we have a network (

V, E

) with a single source 1 and a single sink

n

.

There is no costs in transportation, but each edge has a capacity. We want to

transport as much stuff from 1 to n as possible.

We can turn this into a minimum-cost flow problem. We add an edge from

n

to 1 with

−

1 cost and infinite capacity. Then the minimal cost flow will

maximize the flow from

n

to 1 as possible. So the same amount of stuff will

have to flow from 1 to n through the network.

We can write this is problem as

maximize δ subject to

X

j:(i,j)∈E

x

ij

−

X

j(j,i)∈E

x

ji

=

δ i = 1

−δ i = n

0 otherwise

for each i

0 ≤ x

ij

≤ C

ij

for each (i, j) ∈ E.

Here δ is the total flow from 1 to n.

While we can apply our results from the minimum-cost flow problem, we

don’t have to do so. There are easier ways to solve the problem, using the

max-flow min-cut theorem.

First we need to define a cut.

Definition

(Cut)

.

Suppose

G

= (

V, E

) with capacities

C

ij

for (

i, j

)

∈ E

. A cut

of G is a partition of V into two sets.

For S ⊆ V , the capacity of the cut (S, V \ S) is

C(S) =

X

(i,j)∈(S×(V \S))∩E

C

ij

,

All this clumsy notation says is that we add up the capacities of all edges from

S to V \ S.

Assume

x

is a feasible flow vector that sends

δ

units from 1 to

n

. For

X, Y ⊆ V , we define

f

x

(X, Y ) =

X

(i,j)∈(X×Y )∩E

x

ij

,

i.e. the overall amount of flow from X to Y .

For any solution

x

ij

and cut

S ⊆ V

with 1

∈ S, n ∈ V \ S

, the total flow

from 1 to n can be written as

δ =

X

i∈S

X

j:(i,j)∈E

x

ij

−

X

j:(j,i)∈E

x

ji

.

This is true since by flow conservation, for any

i 6

= 1,

P

j:(i,j)∈E

x

ij

−

P

j:(j,i)∈E

x

ji

= 0,

and for i = 1, it is δ. So the sum is δ. Hence

δ = f

x

(S, V ) − f

x

(V, S)

= f

x

(S, S) + f

x

(S, V \ S) − f

x

(V \ S, S) − f

x

(S, S)

= f

x

(S, V \ S) − f

x

(V \ S, S)

≤ f

x

(S, V \ S)

≤ C(S)

This says that the flow through the cut is less than the capacity of the cut, which

is obviously true. The less obvious result is that this bound is tight, i.e. there is

always a cut S such that δ = C(S).

Theorem (Max-flow min-cut theorem). Let δ be an optimal solution. Then

δ = min{C(S) : S ⊆ V, 1 ∈ S, n ∈ V \ S}

Proof.

Consider any feasible flow vector

x

. Call a path

v

0

, · · · , v

k

an augmenting

path if the flow along the path can be increased. Formally, it is a path that

satisfies

x

v

i−1

v

i

< C

v

i−1

v

i

or x

v

i

v

i−1

> 0

for

i

= 1

, · · · , k

. The first condition says that we have a forward edge where

we have not hit the capacity, while the second condition says that we have a

backwards edge with positive flow. If these conditions are satisfied, we can

increase the flow of each edge (or decrease the backwards flow for backwards

edge), and the total flow increases.

Now assume that x is optimal and let

S = {1} ∪ {i ∈ V : there exists an augmenting path from 1 to i}.

Since there is an augmenting path from 1 to

S

, we can increase flow from 1 to

any vertex in S. So n 6∈ S by optimality. So n ∈ V \ S.

We have previously shown that

δ = f

x

(S, V \ S) − f

x

(V \ S, S).

We now claim that

f

x

(

V \ S, S

) = 0. If it is not 0, it means that there is a node

v ∈ V \ S

such that there is flow from

v

to a vertex

u ∈ S

. Then we can add

that edge to the augmenting path to u to obtain an augmenting path to v.

Also, we must have

f

x

(

S, V \ S

) =

C

(

S

). Or else, we can still send more

things to the other side so there is an augmenting path. So we have

δ = C(S).

The max-flow min-cut theorem does not tell us how to find an optimal path.

Instead, it provides a quick way to confirm that our path is optimal.

It turns out that it isn’t difficult to find an optimal solution. We simply keep

adding flow along augmenting paths until we cannot do so. This is known as

the Ford-Fulkerson algorithm.

(i) Start from a feasible flow x, e.g. x = 0.

(ii) If there is no augmenting path for x from 1 to n, then x is optimal.

(iii)

Find an augmenting path for

x

from 1 to

n

, and send a maximum amount

of flow along it.

(iv) GOTO (ii).

Example. Consider the diagram

- -

1 n

5

1

1

5

2

5

4

We can keep adding flow until we reach

- -

1 n

5

1

1

5

2

5

4

4

1

1

2

2

5

3

(red is flow, black is capacity). We know this is an optimum, since our total flow

is 6, and we can draw a cut with capacity 6:

- -

1 n

5

1

1

5

2

5

4