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:

1. The smallest number of arcs on any flow-aumenting [math]\displaystyle{ (s,t) }[/math]-path increases (non-strictly) monotonously.
2. 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

The correctness proof of Ford-Fulkerson proves the invariant. So, we have to show the variant. In the following, we focus on the residual network [math]\displaystyle{ (G_f,u_f) }[/math].

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 with respect to the current flow. At least one arc of [math]\displaystyle{ p }[/math] will be saturated in this iteration and, thus, leave the residual network. Therefore, it remains 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 if a new arc enters the residual network. This must be an arc [math]\displaystyle{ (w,v) }[/math] such that [math]\displaystyle{ (v,w) }[/math] is an arc of [math]\displaystyle{ p }[/math].

Suppose a new flow-augmenting path [math]\displaystyle{ p' }[/math] has been created. We have to show that [math]\displaystyle{ p' }[/math] has more than [math]\displaystyle{ k }[/math] arcs. Then [math]\displaystyle{ p' }[/math] contains [math]\displaystyle{ r\geq 1 }[/math] arcs as specified in the last paragraph (that is, arcs opposite to arcs on [math]\displaystyle{ p }[/math]). Let [math]\displaystyle{ (w_1,v_1),\ldots,(w_r,v_r) }[/math] denote these arcs, in the order in which they appear on [math]\displaystyle{ p' }[/math] (not necessarily the order in which the opposite arcs appear on [math]\displaystyle{ p }[/math]). For notational convenience, let [math]\displaystyle{ v_0:=s }[/math] and [math]\displaystyle{ w_{r+1}:=t }[/math].

For [math]\displaystyle{ i\in\{0,\ldots,r\} }[/math], let [math]\displaystyle{ p_i }[/math] denote the subpath of [math]\displaystyle{ p' }[/math] from [math]\displaystyle{ v_i }[/math] to [math]\displaystyle{ w_{i+1} }[/math]. Now, for all paths [math]\displaystyle{ p_i }[/math] such that [math]\displaystyle{ w_{i+1} }[/math] appears after [math]\displaystyle{ v_i }[/math] on [math]\displaystyle{ p }[/math], the specific choice of [math]\displaystyle{ p }[/math] to have a minimum number of arcs implies that [math]\displaystyle{ p_i }[/math] does not have fewer arcs than the subpath of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ v_i }[/math] to [math]\displaystyle{ w_{i+1} }[/math]. For the other subpaths [math]\displaystyle{ p_i }[/math], it suffices to note the trivial fact that the number of arcs on [math]\displaystyle{ p_i }[/math] is not negative. Note that for each arc [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math], there is at least one [math]\displaystyle{ i\in\{1,\ldots,r\} }[/math] such that [math]\displaystyle{ v_i }[/math] precedes [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math] and [math]\displaystyle{ w_{i+1} }[/math] succeeds [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math]. So, summing up the numbers of arcs on all [math]\displaystyle{ p_i }[/math] and adding the number [math]\displaystyle{ r }[/math] of arcs [math]\displaystyle{ (w_i,v_i) }[/math] to get the number of arcs on [math]\displaystyle{ p' }[/math] proves the claim.

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.

Remark: The number of nodes is irrelevant for the complexity of an iteration because at most [math]\displaystyle{ m }[/math] nodes are reachable from [math]\displaystyle{ s }[/math] (not including [math]\displaystyle{ s }[/math] itself).