Blocking flow by Dinic: Difference between revisions
| (24 intermediate revisions by the same user not shown) | |||
| Line 14: | Line 14: | ||
'''Break condition:''' | '''Break condition:''' | ||
There is no more [[Basic flow definitions#Flow-augmenting | There is no more [[Basic flow definitions#Flow-augmenting paths and saturated arcs|flow-augmenting]] [[Basic graph definitions#Paths|ordinary <math>(s,t)</math>-path]] in <math>G</math>. | ||
== Induction basis == | == Induction basis == | ||
| Line 30: | Line 30: | ||
'''Abstract view:''' | '''Abstract view:''' | ||
# Run a [[Depth-first search|DFS]] from <math>s</math> | # Run a [[Depth-first search|DFS]] from <math>s</math> with two modifications: (1) The search may [[Graph traversal#Remarks|terminate early]], namely when <math>t</math> is seen; (2) whenever the search goes backwards from some node, this node and all of its incident arcs are removed from <math>G</math>. | ||
# If <math>t</math> is ''not'' seen, the break condition applies, and the algorithm is terminated. | # If <math>t</math> is ''not'' seen, the break condition applies, and the algorithm is terminated. | ||
# Otherwise: | # Otherwise: | ||
## Let <math>p</math> be the <math>(s,t)</math>-path found in step 1. | ## Let <math>p</math> be the ordinary <math>(s,t)</math>-path found in step 1. | ||
## Let <math>\Delta</math> be the minimum of the values <math>u(a)</math> of all arcs <math>a</math> on <math>p</math>. | ## Let <math>\Delta</math> be the minimum of the values <math>u(a)</math> of all arcs <math>a</math> on <math>p</math>. | ||
## For each arc <math>a</math> on <math>p</math>: | ## For each arc <math>a</math> on <math>p</math>: | ||
### Increase <math>f(a)</math> by <math>\Delta</math> and decrease <math>u(a)</math> by <math>\Delta</math>. | ### Increase <math>f(a)</math> by <math>\Delta</math> and decrease <math>u(a)</math> by <math>\Delta</math>. | ||
### If <math>u(a)=0</math>, remove <math>a</math> from <math>G</math>. | ### If <math>u(a)=0</math>, remove <math>a</math> from <math>G</math>. | ||
'''Proof:''' | '''Proof:''' | ||
Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an <math>(s,t)</math>, and from the specific choice of <math>\Delta</math> | Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an <math>(s,t)</math>-path, and from the specific choice of <math>\Delta</math>. Also, the specific choice of <matH>\Delta</math> ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2. | ||
== Correctness == | |||
The variant implies termination. Since the graph is acyclic and the arcs are only considered in forward direction by the DFS, a node <math>v\in V</math> is indeed removed only if there is no flow-augmenting ordinary <math>(v,t)</math>-path. Hence, the set of flow-augmenting ordinary <math>(s,t)</math>-paths is not reduced by the node removals. So, the break condition, though applied to the reduced graph, also implies for the original graph that the flow is blocking on termination. | |||
== Complexity == | == Complexity == | ||
'''Statement:''' | '''Statement:''' | ||
The | The asymptotic complexity is in <math>\mathcal{O}(n\cdot m)</math>, where <math>n=|V|</math> and <math>m=|A|</math>, | ||
'''Proof:''' | |||
Due to the variant, the number of iterations is linear in the number of arcs. The second modification of the search in step 1 ensures that the total number of backward steps over all iterations of the main loop is linear in the number of nodes. The number of forward steps within one iteration is linear in the number of nodes because every node is removed before it can be seen a second time. | |||
Latest revision as of 08:37, 7 December 2015
General information
Algorithmic problem: Blocking flow.
Type of algorithm: loop.
Abstract view
Invariant: The current flow is feasible.
Variant: The number of arcs decreases.
Break condition: There is no more flow-augmenting ordinary [math]\displaystyle{ (s,t) }[/math]-path in [math]\displaystyle{ G }[/math].
Induction basis
Abstract view: Initialize [math]\displaystyle{ f }[/math] to be a feasible flow, for example, the zero flow.
Implementation: Obvious.
Proof: Obvious.
Induction step
Abstract view:
- Run a DFS from [math]\displaystyle{ s }[/math] with two modifications: (1) The search may terminate early, namely when [math]\displaystyle{ t }[/math] is seen; (2) whenever the search goes backwards from some node, this node and all of its incident arcs are removed from [math]\displaystyle{ G }[/math].
- If [math]\displaystyle{ t }[/math] is not seen, the break condition applies, and the algorithm is terminated.
- Otherwise:
- Let [math]\displaystyle{ p }[/math] be the ordinary [math]\displaystyle{ (s,t) }[/math]-path found in step 1.
- Let [math]\displaystyle{ \Delta }[/math] be the minimum of the values [math]\displaystyle{ u(a) }[/math] of all arcs [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math].
- For each arc [math]\displaystyle{ a }[/math] on [math]\displaystyle{ p }[/math]:
- Increase [math]\displaystyle{ f(a) }[/math] by [math]\displaystyle{ \Delta }[/math] and decrease [math]\displaystyle{ u(a) }[/math] by [math]\displaystyle{ \Delta }[/math].
- If [math]\displaystyle{ u(a)=0 }[/math], remove [math]\displaystyle{ a }[/math] from [math]\displaystyle{ G }[/math].
Proof: Feasibility of the flow follows immediately from the fact that the flow is increased by a constant amount over an [math]\displaystyle{ (s,t) }[/math]-path, and from the specific choice of [math]\displaystyle{ \Delta }[/math]. Also, the specific choice of [math]\displaystyle{ \Delta }[/math] ensures that at least one arc is saturated in step 3.3.1 and, hence, removed in step 3.3.2.
Correctness
The variant implies termination. Since the graph is acyclic and the arcs are only considered in forward direction by the DFS, a node [math]\displaystyle{ v\in V }[/math] is indeed removed only if there is no flow-augmenting ordinary [math]\displaystyle{ (v,t) }[/math]-path. Hence, the set of flow-augmenting ordinary [math]\displaystyle{ (s,t) }[/math]-paths is not reduced by the node removals. So, the break condition, though applied to the reduced graph, also implies for the original graph that the flow is blocking on termination.
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n\cdot m) }[/math], where [math]\displaystyle{ n=|V| }[/math] and [math]\displaystyle{ m=|A| }[/math],
Proof: Due to the variant, the number of iterations is linear in the number of arcs. The second modification of the search in step 1 ensures that the total number of backward steps over all iterations of the main loop is linear in the number of nodes. The number of forward steps within one iteration is linear in the number of nodes because every node is removed before it can be seen a second time.