Edmonds-Karp

From Algowiki
Jump to: navigation, search

General Information

Algorithmic problem: Max-flow problems (standard version)

Algorithm : This is a specialization of Ford-Fulkerson: Among all flow-augmenting paths [math](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](s,t)[/math]-flow, let [math]A_f[/math] denote the set of all arcs that belong to at least one flow-augmenting [math](s,t)[/math]-path with smallest number of arcs.

Variant:

  1. The smallest number of arcs on any flow-aumenting [math](s,t)[/math]-path increases (non-strictly) monotonously.
  2. Whenever that number does not increase in an iteration, the size of [math]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](G_f,u_f)[/math].

Let [math]p[/math] be the flow-augmenting path in the current iteration, and let [math]k[/math] be the number of arcs on [math]p[/math]; in other words, the minimum number of arcs of a flow-augmenting [math](s,t)[/math]-path with respect to the current flow. At least one arc of [math]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]p[/math] according to Ford-Fulkerson does not create new flow-augmenting paths of length [math]k[/math] or less than [math]k[/math].

A new flow-augmenting [math](s,t)[/math]-path can only be created if a new arc enters the residual network. This must be an arc [math](w,v)[/math] such that [math](v,w)[/math] is an arc of [math]p[/math].

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

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

Complexity

Statement: In any case (even if the upper bounds are not integral), the asymptotic complexity is in [math]\mathcal{O}(nm^2)[/math] in the worst case, where [math]n=|V|[/math] and [math]m=|A|[/math].

Proof: The variant implies that the smallest number of arcs on a flow-augmenting path strictly increases after at most [math]m[/math] iterations. This number is positive, but cannot be larger than [math]n-1[/math]. Hence, the total number of iterations is in [math]\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]m[/math] nodes are reachable from [math]s[/math] (not including [math]s[/math] itself).