Edmonds-Karp: Difference between revisions
| Line 37: | Line 37: | ||
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. Note that <math>p'</math> contains <math>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>(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 they appear on <math>p</math>). For notational convenience, let <math>v_0:=s</math> and <math>w_{r+1}:=t</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. Note that <math>p'</math> contains <math>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>(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 they 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 | 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 09:42, 13 October 2014
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:
- The flow [math]\displaystyle{ f }[/math] is a fleasible flow.
- 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:
- The smallest number of arcs on a flow-aumenting [math]\displaystyle{ (s,t) }[/math]-path increases (non-strictly) monotonously.
- 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 with respect to the current flow. At least one arc is saturated and, thus, not on any flow-augmenting path anymore. 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 by an arc of [math]\displaystyle{ p }[/math] that fulfills one of the following two conditions immediately before the current iteration:
- A forward arc [math]\displaystyle{ (v,w)\in A }[/math] of [math]\displaystyle{ p }[/math] with [math]\displaystyle{ f(v,w)=0 }[/math].
- 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 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. Note that [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 [math]\displaystyle{ p' }[/math] (not necessarily the order in which they 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.