PDF of Eric’s handwritten notes are here.

**Max-flow problem**

Sending supply (e.g., internet traffic, products) from vertex to vertex without exceeding edge capacities.

**Flow network**

directed graph with designated source and sink ; a capacity for each .

is the flow along the edge . We want to maximize the flow from to .

Constraints:

- for all , (capability constraint)
- for all , flow-in = flow-out : (flow is conserved)

= total flow sent = flow-out = = flow-in = .

**Simple algorithm idea**

(see handwritten notes for an example)

- start with for all
- find an s-t path with available capacity
- increase the flow along until some edge hits its capacity
- repeat until no such s-t path exists

**Residual network**

For a flow network on with capacities and flow , residual network has edges:

- if and , then add to with capacity
- if and , then add to with capacity

**Ford-Fulkerson algorithm**

- set for all
- build the residual network for the current for
- check for a s-t path in , if there is no such path, return as the output
- let be the minimum capacity along in
- augment along by :
- for a forward edge , increases by
- for a backward edge , decrease by

- repeat from 2.

**Runtime**

If capacities are integers, then the flow increases by unit each iteration. So if = size of max-flow, it requires iterations.

Each iteration involves a DFS or BFS, so takes time (assuming is connected). So the runtime is . This is *pseudo*-polynomial since it depends on the numbers in the input.

Better algorithm: [Edmonds-Karp ’72] takes the shortest augmenting path in , which results in rounds, total time.

For a graph , a cut is a partition . For a directed with two vertices , s-t cut is a partition where .

The capacity of a s-t cut is .

Fact: for every flow and every s-t cut , .

**Max-flow min-cut theorem**

.

We”ll show this theorem by proving that for a flow , if there is no augmenting path in the residual network, then there is a s-t cut where . Hence . This also shows that Ford-Fulkerson finds a max-flow.