Max Flow - Min Cut

Skip to main content

Section 7.2 Max Flow - Min Cut

In this section, we consider an algorithm which solves for the maximum flow. We also discuss cuts, and show how duality connects flows and cuts.

Exploration 7.2.1.

Recall Exploration 7.1.1. Suppose that we wish to install a toll booth on these bridges so that each person going to

v_{5}

pays a toll at least once. The cost of installing a toll booth on a bridge is proportional to it’s capacity.

(a)

Find three different ways to install these booths, and find what you believe is the cheapest way to do so.

Definition 7.2.2.

Given a capacitated network

N,

a cut of

N

is a partition of the vertex set into non-empty subsets

C = (V_{1}, V_{2}),

where

V = V_{1} ⊔ V_{2}, v_{s} \in V_{1}, v_{d} \in V_{2} .

The capacity of a cut

C

is the sum

\sum_{v_{i} \in V_{1}, v_{j} \in V_{2}} c_{i j} .

Activity 7.2.3.

(a)

From Exploration 7.1.1, find three different cuts and their capacities.

(b)

What cut do you think minimizes the capacity, how does this compare to your conjectured max flow for this problem?

Activity 7.2.4.

Consider the primal maximization problem for a max flow problem for a capacitated network with unique source

v_{s}

and unique sink

v_{d} :

\begin{aligned} Maximize: \sum_{i} x_{i d} \\ subject to: \sum_{i} x_{i j} - \sum_{i} x_{j i} & = 0, for each vertex v_{j} \\ x_{i j} & \leq c_{i j}, for each edge (v_{i}, v_{j}) \\ x_{i j} & \geq 0, for each edge (v_{i}, v_{j}) . \end{aligned}

(a)

Consider the dual problem for this maximization problem where

μ_{j}

is the unconstrained dual variable for the vertex equality constraint and the

y_{i j}

is the dual variable for the capacity constraint. Verify that this problem may be written as

\begin{aligned} Minimize: \sum_{(v_{i}, v_{j}) \in E} c_{i j} y_{i j} \\ subject to: μ_{j} + y_{s j} & \geq 0, for each edge (v_{s}, v_{j}) \\ - μ_{i} + μ_{j} + y_{i j} & \geq 0, for each edge (v_{i}, v_{j}), i \neq s, j \neq d \\ - μ_{i} + y_{i d} & \geq 1, for each edge (v_{i}, v_{d}) \\ y_{i j} & \geq 0, for each edge (v_{i}, v_{j}) \end{aligned}

where

μ_{s} = 0, μ_{d} = - 1 .

(b)

Verify that we may simplify the dual solution as:

\begin{aligned} Minimize: \sum_{(v_{i}, v_{j}) \in E} c_{i j} y_{i j} \\ subject to: - μ_{i} + μ_{j} + y_{i j} & \geq 0, for each edge (v_{i}, v_{j}) \\ μ_{s} & = 0 \\ μ_{d} & = - 1 \\ y_{i j} & \geq 0, for each edge (v_{i}, v_{j}) . \end{aligned}

(c)

Suppose

μ_{j} = - 1 .

What could

μ_{i}, y_{i j}

be? What value for

μ_{i}

would minimize the dual objective function? What happens if

μ_{i}

is huge? How would the resulting

μ_{i}

that affect the inequality

- μ_{k} + μ_{i} + y_{k i} \geq 0 ?

Repeat for

μ_{i} = 0, μ_{j} = - 1, 0 .

(d)

Suppose each

μ_{k} \in {0, - 1},

Note that

V_{1} := {v_{i} : μ_{i} = 0}, V_{2} := {v_{j} : μ_{j} = - 1}

forms a cut of

N .

For

v_{i}, v_{j} \in V_{1},

what is the

y_{i j}

that minimizes the objective function?

For

v_{i}, v_{j} \in V_{2},

what is the

y_{i j}

that minimizes the objective function?

For

v_{i} \in V_{1}, v_{j} \in V_{2},

what is the

y_{i j}

that minimizes the objective function?

For

v_{i} \in V_{2}, v_{j} \in V_{1},

what is the

y_{i j}

that minimizes the objective function?

Can any cut of

N

be modeled this way?

(e)

What is the capacity of the above cut? How does that relate to the dual problem?

(f)

Prove that the maximum flow through a network is bounded above by the minimum cut capacity.

Activity 7.2.5.

We explore a way of generating potential minimum cuts using a maximum flow.

Recall Exploration 7.1.1 and your proposed maximum flow

f^{'} .

(a)

Let

v_{0} \in V_{1}^{'},

we recursively define

V_{1}^{'}

by adding

v_{j}

to

V_{1}^{'}

if either:

$v_{i} \in V_{1}^{'}, (v_{i}, v_{j}) \in E, x_{i j}^{'} < c_{i j} .$
$v_{i} \in V_{1}^{'}, (v_{j}, v_{i}) \in E, x_{j i}^{'} > 0 .$

(b)

Let

V_{2}^{'} := V ∖ V_{1}^{'} .

What is the cut capacity of

(V_{1}^{'}, V_{2}^{'}) ?

Activity 7.2.6.

We now prove that the minimum cut capacity is equal to the maximum flow.

(a)

Why does the primal max problem achieve optimality?

Call the maximum flow

f^{'},

with flow on each edge

x_{i j}^{'} .

(b)

Let

v_{s} \in V_{1}^{'},

we recursively define

V_{1}^{'}

by adding

v_{j}

to

V_{1}^{'}

if either:

$v_{i} \in V_{1}^{'}, (v_{i}, v_{j}) \in E, x_{i j}^{'} < c_{i j} .$
$v_{i} \in V_{1}^{'}, (v_{j}, v_{i}) \in E, x_{j i}^{'} > 0 .$

and repeating until we stabilize, why must we eventually stabilize?

(c)

Show that for any

v_{k}

in

V_{1}^{'},

there is an

α

-path

P :

a sequence of vertices starting

v_{s}

to

v_{k},

where between

v_{i}, v_{j}

either

(v_{i}, v_{j}), (v_{j}, v_{i}) \in E .

$An \(\alpha\)-path.$

We would call the edges

(v_{i}, v_{j})

to be forward edges and

(v_{j}, v_{i})

backwards edges of

P .

(d)

Suppose (by way of contradiction) that

v_{d} \in V_{1}^{'} .

There is by (c) an

α

-path

P

from

v_{s}

to

v_{d} .

Let

q := min {min_{(v_{i}, v_{j}) a forward edge} {c_{i j} - x_{i j}^{'}}, min_{(v_{j}, v_{i}) a backwards edge} {x_{j i}^{'}}} .

Why is

q > 0 ?

(e)

We define a new flow

f^{″}

as follows: for each forward edge of

P,

(v_{i}, v_{j}),

we add

x_{i j}^{″} = q + x_{i j}^{'} .

For each backwards edge

(v_{j}, v_{i})

we subtract

x_{j i}^{″} = x_{j i}^{'} - q .

Explain why this is still a valid network flow.

(f)

Explain why

f^{″}

has a greater value than

f^{'} .

Why must

v_{d} \notin V_{1}^{'} ?

(g)

Define

V_{2}^{'} = V ∖ V_{1}^{'} .

Prove that for any

v_{i} \in V_{1}^{'}, v_{j} \in V_{2}^{'},

we have that

x_{i j}^{'} = c_{i j}, x_{j i}^{″} = 0 .

(Not neccesary for this proof, but to tie things in, if

x_{i j}^{″} = c_{i j},

what does that say about

y_{i j}

from the dual problem in Activity 7.2.4? If

x_{i j}^{'} < c_{i j},

what does that say about

y_{i j} ?

)

(h)

Use the result from Exercise 7.4.5 to show that the value of

f^{'}

is equal to the cut capacity of

(V_{1}^{'}, V_{2}^{'}) .

(Proving the result!)

(i)

Going back to Activity 7.2.4 if we let

μ_{i} = 0

for

v_{i} \in V_{1}^{'}

and

μ_{j} = - 1

for

v_{j} \in V_{2}^{'},

what is the value of the dual min objective?

Theorem 7.2.7. Max Flow-Min Cut.

Let

N = (V, E)

be a capacitated directed network with unique fixed source and unique fixed sink, no edges into the source, and no edges out of the sink. Then the value of the maximalflow from

v_{s}

to

v_{d}

is equal to the minimal cut capacity in

N .

Activity 7.2.8.

Suppose we had a non-optimal flow

f,

how could we adopt the procedure in Activity 7.2.6 to obtain a better flow?

Subsection 7.2.1 Algorithms for Max Flow and Min Cut

Exploration 7.2.9.

Consider the following capacitated network with source

v_{0}

and sink

v_{5} :

$A network with multiple sources and sinks.$

Recall the procedure to produce improved flows in Activity 7.2.6.

(a)

Begin with the zero-flow.

$A network with multiple sources and sinks.$

Consider the

α

-path

v_{0} v_{2} v_{4} v_{5} .

Apply Activity 7.2.6 (d) to this path. What is

q ?

(b)

Adjust the flow on edges by

q

appropriately. Explain why we need not consider the edge

v_{2} v_{4}

for any future

α

-paths.

(c)

Pick another

α

-path where

q > 0

and repeat until we achieve a maximum flow.

Hint.

$A network with multiple sources and sinks.$

(d)

Use the maximum flow and the argument in Activity 7.2.6 to find a minimum cut.

Definition 7.2.10. Ford-Fulkerson Algorithm.

We describe an algorithm to find the maximum flow for

N,

a capacitated network with a unique source

v_{s}

and sink

v_{d} :

INITIALIZE: We begin with any feasible flow $f$ (including the zero flow.)
Pick an $α$ -path $P$ in $N$ from $v_{s}$ to $v_{d}$ such that:
- Each forward edge of $P$ satisfies $x_{i j} < c_{i j} .$
- Eack backwards edge satisfies $x_{i j} > 0 .$
(If no such $α$ -path $P$ exists, GOTO 5)
Compute

$q := min {min_{(v_{i}, v_{j}) a forward edge} {c_{i j} - x_{i j}^{'}}, min_{(v_{j}, v_{i}) a backwards edge} {x_{j i}^{'}}} .$
Define a new flow $f^{'}$ as follows: for each forward edge of $P,$ $(v_{i}, v_{j}),$ we add $x_{i j}^{'} = q + x_{i j} .$ For each backwards edge $(v_{j}, v_{i})$ we subtract $x_{j i}^{'} = x_{j i} - q .$

Let $f := f^{'}$ and GOTO 2
STOP. The flow is now optimal.

Activity 7.2.11.

Prove that the Ford-Fulkerson Algorithm Definition 7.2.10 terminates at a maximum flow.

Definition 7.2.12. Min Cut Algorithm.

We describe an algorithm to find the minimum for

N,

a capacitated network with a unique source

v_{s}

and sink

v_{d} :

INITIALIZE: We begin with a maximum flow $f^{'}$ and $V_{1} = {v_{s}} .$
We add $v_{j}$ to $V_{1}$ if there is a $v_{i} \in V_{1}$ such that either:
- $(v_{i}, v_{j}) \in E, x_{i j}^{'} < c_{i j} .$
- $(v_{j}, v_{i}) \in E, x_{j i}^{'} > 0 .$
If there is no such $v_{i},$ GOTO 4
GOTO 2
Let $V_{2} = V ∖ V_{1} .$

STOP $(V_{1}, V_{2})$ form a minimum cut.