Ford-Fulkerson: PDF of Eric’s handwritten notes are here.

Edmonds-Karp: 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:

*Capacity constraint:*for all ,*Conservation of flow:*for all , flow-in = flow-out , in other words:

= 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

This approach doesn’t work, since sometimes need to decrease flow along some edges to increase the total flow (see the handwritten notes for such an example).

**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 step 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). Therefore the overall runtime is . This is *pseudo*-polynomial since it depends on the numbers in the input. We want the running time to be independent of the capacities and the size of the flow.

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

**Edmonds-Karp algorithm**

This algorithm finishes in at most rounds and thus reaches overall running time . It also works with any positive capacities (remember that Ford-Fulkerson algorithm requires capacities to be integers).

Edmonds-Karp algorithm is identical to Ford-Fulkerson algorithm except **Step 3:**

3. Run BFS in and take the path with fewest edges.

To analyze the running time of the Edmonds-Karp algorithm, we are going to prove the following two claims:

- a) in every round, at least one edge is deleted from
- b) an edge is added or deleted from at most times

Hence, since there are edges, the number of rounds will be no more than .

For **Claim a)**, at least one edge in is fully occupied since is the min residual capacity along . And such will be deleted afterwards.

For **Claim b)**, let’s see what happened when an edge is added to or deleted from :

- if is a forward edge then
- is deleted if it is fully occupied (i.e. )
- is added if previously

- if is a backward edge then
- is deleted if flow on it is removed (i.e. )
- is added if previously

In , let minimum number of edges in paths from to . Note that is changing so may also changes.

**Claim:** does not decrease during the execution of the algorithm

**Proof:** Note that in step 3 we take the shortest path .

Let where . We know that .

Consider the relation between and :

- by definition of
- since otherwise there exist a shorter path

Thus we know and in .

For any decreases iff some edge is added where so makes nearer to . However, in order to add such to , must be in the shortest path first. Thus we know .

So must stay the same or increase during the execution of the algorithm.

Now consider what happens if an edge is deleted from and later added into :

- When it is deleted we know
- When it is added later we know

Since never decrease we know . Which means if an edge is deleted and added later then at least increases by 2.

Thus an edge can be deleted and added later for no more than times since .

And remember that at least 1 edge is deleted each round we know the total number of rounds is no more than .

Thus the overall running time of Edmonds-Karp algorithm is .

The current best algorithm for the max-flow problem runs in time by [Orlin ’13].