Edmonds-Karp Algorithm

Summary

Edmonds-Karp is an example of a Ford-Fulkerson algorithm that solves a max-flow problem.

Contents

• Max Flow Min Cut Algorithms
• Ford-Fulkerson Review
• Edmonds-Karp Algorithm
  • Proof outline
    • BFS Properties
  • Adding and Deleting Edges
• Proof of Claim

Max Flow Min Cut Algorithms

• Ford-Fulkerson
  • Find augmenting paths (from s to t) using DFS or BFS
  • O(mC)
    • C is size of max flow
  • Assumes integer capacities
• Edmonds-Karp
  • Finds augmenting paths using BFS
  • $O(m^2n)$
  • No assumptions on capacities

Ford-Fulkerson Review

Input: Flow network G=(V,E) with integer capacities

1. Set $\forall e \in E, f_e = 0$
2. Build residual network $G^f$
3. Check for st-path P in $G^f$ using BFS or DFS
4. If no such path, return f
5. Let c(P) = min capacity along P in $G^f$
6. Augment f by c(P) units along P
7. Repeat to 2 until no st-path

Edmonds-Karp Algorithm

Input: Flow network G=(V,E) with _integer capacities

1. Set $\forall e \in E, f_e = 0$
2. Build residual network $G^f$
3. Check for st-path P in $G^f$ using BFS _{or DFS}
4. If no such path, return f
5. Let c(P) = min capacity along P in $G^f$
6. Augment f by c(P) units along P
7. Repeat to 2 until no st-path

At least one edge is removed every round (when edge reaches full capacity)

Proof outline

In order to prove that runtime is $O(m^2n)$, we’re going to prove the # of rounds is $\le mn$

BFS runs in linear time, so running it mn times gives us $O(m^2n)$

In every round, residual graph changes, at least one edge is deleted

Key lemma: For every edge e, e is deleted and reinserted later $\le \frac{n}{2}$ times

Since there are m edges, and the lemma holds for every edge, there are $\le \frac{nm}{2}$ total rounds

BFS Properties

BFS Input: directed graph G=(V,E), no edge weights, $s \in V$

Output: $\forall v \in V, \text{dist}(v) = \text{ min # of edges } s \leadsto v$

$\text{level}(v) = \text{ dist}(v) = \text{ min # of edges } s \leadsto v$

$P = s \rightarrow a \rightarrow d \rightarrow t$

$P = ^{0}_{s} \rightarrow ^{1}_a \rightarrow ^2_d \rightarrow ^3_t$

Level goes up by 1 each vertex. It cannot go up by more than one because definitionally the level is the minimum. It cannot stay the same or go down, otherwise there’s a shorter path.

How does a level change as the residual network changes?

A level can go up by removing an edge

Adding and Deleting Edges

How does $G^f$ change in a round?

For $\overrightarrow{vw}$:

• add $\overrightarrow{vw}$ if flow was full and then reduced
  • so $\overrightarrow{wv} \in P$
• remove $\overrightarrow{vw}$ if flow is now full
  • so $\overrightarrow{vw} \in P$
• add $\overrightarrow{wv}$ if flow was empty then increase
  • so $\overrightarrow{vw} \in P$
• remove $\overrightarrow{wv}$ if flow is now emtpy
  • so $\overrightarrow{vw} \in P$

Proof of Claim

Claim: For every $z \in V$, level(z) does not decrease

It might decrease if we add edge $\overrightarrow{yz}$

Suppose level(z) = i, add $\overrightarrow{yz}$ to $G^f$ so $\overrightarrow{zy} \in P$

• BFS Path
  • level(y) = level(z) + 1

If the level of y is < z, then we would have already included it in the BFS path to z. Anything else must mean $level(y) \ge level(z)$ which means adding the new edge will be at least level(z) + 1

Deleting then readding an edge from the residual graph strictly increases the level