Edmonds-Karp
General Information
Algorithmic problem: Max-flow problems (standard version)
Algorithm : This is a specialization of Ford-Fulkerson: Among all flow-augmenting paths [math]\displaystyle{ (s,t) }[/math]-paths, always choose one with smallest number of arcs. Consequently, a BFS is applied to find the path.
Abstract View
Invariant: identical to the invariant of Ford-Fulkerson.
Notation: For an [math]\displaystyle{ (s,t) }[/math]-flow, let [math]\displaystyle{ A_f }[/math] denote the set of all arcs that belong to at least one flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path with smallest number of arcs.
Variant:
- The smallest number of arcs on any flow-aumenting [math]\displaystyle{ (s,t) }[/math]-path increases (non-strictly) monotonously.
- Whenever that number does not increase in an iteration, the size of [math]\displaystyle{ A_f }[/math] decreases in that iteration.
Break condition: There is no flow-augumenting path.
Correctness
See Ford-Fulkerson.
Complexity
Statement: Even if the upper bounds are not integral, the asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(nm^2) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math].
Proof: The variant implies that the smallest number of arcs on a flow-augmenting path strictly increases after at most [math]\displaystyle{ m }[/math] iterations. This number is positive, but cannot be larger than [math]\displaystyle{ n-1 }[/math]. Hence, the total number of iterations is in [math]\displaystyle{ \mathcal{O}(nm) }[/math]. The claim then follows from the fact that the complexity of an iteration is linear in the number of arcs.