Edmonds-Karp: Difference between revisions

From Algowiki
Jump to navigation Jump to search
 
(23 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== General Information ==
== General Information ==


'''Algorithmic problem:''' [[Max-Flow Problems]]
'''Algorithmic problem:''' [[Max-Flow Problems#Standard version|Max-flow problems (standard version)]]


'''Algorithm :''' This is a minor variation of [[Ford-Fulkerson]]: Among all flow-augmenting <math>(s,t)</math>-paths, always choose one with smallest number of arcs.
'''Algorithm :''' This is a specialization of [[Ford-Fulkerson]]: Among all [[Basic flow definitions#Flow augmenting paths and saturated arcs|flow-augmenting paths]] <math>(s,t)</math>-paths, always choose one with smallest number of arcs. Consequently, a [[Breadth-first search|BFS]] is applied to find the path.


== Abstract View ==
== Abstract View ==


'''Invariant:'''
'''Invariant:'''
After <math>i \ge 0</math> iterations:
identical to the invariant of [[Ford-Fulkerson]].
# The flow <math>f</math> is a fleasible flow.
# If all upper bounds are integral, <math>f</math> is integral as well.


'''Notation:'''
'''Notation:'''
Line 16: Line 14:


'''Variant:'''
'''Variant:'''
# The smallest number of arcs on a flow-aumenting <math>(s,t)</math>-path increases (non-strictly) monotonously.
# The smallest number of arcs on any flow-aumenting <math>(s,t)</math>-path increases (non-strictly) monotonously.
# Whenever that number does ''not'' decrease in an iteration, the size of <math>A_f</math> decreases.
# 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.
'''Break condition:''' There is no flow-augumenting path.
== Correctness ==
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, 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 ==
== Complexity ==


'''Statement:'''
'''Statement:'''
Even if the upper bounds are not integral, the asymptotic complexity is in <math>\mathcal{O}(nm^2)</math>, where <math>n=|V|</math> and <math>m=|A|</math>.
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:'''
'''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 is saturated 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 tan <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>w_i</math> to <math>v_{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 tha 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>proves the claim.
'''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).

Latest revision as of 12:34, 1 December 2015

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: In any case (even if the upper bounds are not integral), the asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(nm^2) }[/math] in the worst case, 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).

Retrieved from "https://wiki.algo.informatik.tu-darmstadt.de/index.php?title=Edmonds-Karp&oldid=3671"