PDF of Eric’s handwritten notes are here.

**Recall Max-flow problem**

Given a flow network, find a flow of maximum size.

**Recall Ford-Fulkerson algorithm**

input: flow network with integer capacities for .

- Set for all
- Build residual network :
- for :
- if : add with residual capacity
- if : add with residual capacity

- for :
- Check for a st-path in
- If such path does not exist, return()
- Otherwise, denote minimum residual capacity along in

- Augment by units along
- Repeat from step 2 until no st-path can be found in

**Running time:**

- Let size of max-flow
- The algorithm cost time per round
- There will be at most rounds (since the size of flow increases at least by 1 after every round)
- Overall running time is .

We want the running time to be independent with capacities/size of flows.

**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.

And 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

Since there are totally 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 .

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