Edmonds-Karp

General Information

Algorithmic problem: Max-Flow Problems

Algorithm : This is a minor variation of Ford-Fulkerson: Among all flow-augmenting [math]\displaystyle{ (s,t) }[/math]-paths, always choose one with smallest number of arcs.

Abstract View

Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations:

1. The flow [math]\displaystyle{ f }[/math] is a fleasible flow.
2. If all upper bounds are integral, [math]\displaystyle{ f }[/math] is integral as well.

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:

1. The smallest number of arcs on a flow-aumenting [math]\displaystyle{ (s,t) }[/math]-path increases (non-strictly) monotonously.
2. Whenever that number does not decrease in an iteration, the size of [math]\displaystyle{ A_f }[/math] decreases.

Break condition: There is no flow-augumenting path.

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: If the variant is fulfilled, 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.

Therefore, it suffices to show that the variant is fulfilled. Let [math]\displaystyle{ p }[/math] be the flow-augmenting path in the current iteration, and let [math]\displaystyle{ k }[/math] be the number of arcs on [math]\displaystyle{ p }[/math]; in other words, the minimum number of arcs of a flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path. At least one arc is saturated and, thus, not on any flow-augmenting path anymore. Therefore, it suffices to show that augmenting the flow along [math]\displaystyle{ p }[/math] according to Ford-Fulkerson does not create new flow-augmenting paths of length [math]\displaystyle{ k }[/math] or less than [math]\displaystyle{ k }[/math].

A new flow-augmenting [math]\displaystyle{ (s,t) }[/math]-path can only be created by an arc of [math]\displaystyle{ p }[/math] that fulfills one of the following two conditions immediately before the current iteration:

1. A forward arc [math]\displaystyle{ (v,w)\in A }[/math] of [math]\displaystyle{ p }[/math] with [math]\displaystyle{ f(v,w)=0 }[/math].
2. A backward arc [math]\displaystyle{ (w,v)\in A }[/math] of [math]\displaystyle{ p }[/math] with [math]\displaystyle{ f(w,v)=u(w,v) }[/math].

Suppose for a contradiction that a new flow-augmenting path [math]\displaystyle{ p' }[/math] has been created. Then [math]\displaystyle{ p' }[/math] contains [math]\displaystyle{ r\geq 1 }[/math] arcs that fall into one of the two cases above. For notational convenience (to get rid of that case distinction), we assume without loss of generality that all of these arcs are backward arcs; the treatment of forward arcs is perfectly analogous. So let [math]\displaystyle{ (w_1,v_1),\ldots,(w_r,v_r) }[/math] denote these arcs, in the order in which they appear on the newly created

Let [math]\displaystyle{ v_1,\ldots,v_ }[/math] and Let [math]\displaystyle{ p_1 }[/math] be the subpath of this path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ w }[/math], and [math]\displaystyle{ p_2 }[/math] the subpath from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ t }[/math]. Due to the specific choice of [math]\displaystyle{ p }[/math], [math]\displaystyle{ p_1 }[/math] does not have fewer arcs than the subpath of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ w }[/math], and [math]\displaystyle{ p_2 }[/math] does not have fewer arcs than the subpath of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ t }[/math]. In summary, the newly created path has strictly more arcs than [math]\displaystyle{ p }[/math].

ToDo: extend the proof to the case that more than one arc of [math]\displaystyle{ p }[/math] is on the newly created flow-augmenting path.