Edmonds-Karp: Difference between revisions
| Line 21: | Line 21: | ||
== Correctness == | == Correctness == | ||
The [[Ford-Fulkerson#Correctness|correctness proof of Ford-Fulkerson]] proves the invariant. So, we have to show the variant. | The [[Ford-Fulkerson#Correctness|correctness proof of Ford-Fulkerson]] proves the invariant. So, we have to show the variant. In the following, we focus on the [[Basic flow definitions#Residual network|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, | 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. | 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. | 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. 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>v_{i+1}</math> appears after <math>w_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>w_i</math> to <math>v_{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. 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. | 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>v_{i+1}</math> appears after <math>w_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>w_i</math> to <math>v_{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. 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. | ||
Revision as of 20:06, 9 November 2014
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
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. 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{ v_{i+1} }[/math] appears after [math]\displaystyle{ w_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{ w_i }[/math] to [math]\displaystyle{ v_{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. 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.