|
|
| Line 29: |
Line 29: |
|
| |
|
| '''Proof:''' | | '''Proof:''' |
| If the variant is fulfilled, 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. Therefore, it suffices to show that the variant is fulfilled.
| | 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. |
| | |
| 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> is being saturated in this iteration and, thus, not on any flow-augmenting path anymore. 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 by an arc of <math>p</math> that fulfills one of the following two conditions immediately before the current iteration:
| |
| # A forward arc <math>(v,w)\in A</math> of <math>p</math> with <math>f(v,w)=0</math>.
| |
| # A backward arc <math>(w,v)\in A</math> of <math>p</math> with <math>f(w,v)=u(w,v)</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 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 19:42, 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
See Ford-Fulkerson.
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.