Three indians' algorithm: Difference between revisions
| (30 intermediate revisions by 2 users not shown) | |||
| Line 12: | Line 12: | ||
'''Variant:''' | '''Variant:''' | ||
The number of nodes strictly decreases. | The number of nodes strictly decreases. | ||
'''Break condition:''' | |||
There is no more [[Basic graph definitions#Paths|ordinary <math>(s,t)</math>-path]] in <math>G</math>. | |||
== Induction basis == | == Induction basis == | ||
| Line 27: | Line 30: | ||
'''Implementation:''' | '''Implementation:''' | ||
# For each node <math>v\in V\setminus\{s,t\}</math>, let <math>T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\}</math> | # For each node <math>v\in V\setminus\{s,t\}</math>, let <math>T(v)</math> denote the '''throughput''' of <math>v</math>, which is defined by <math>T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\}</math>. | ||
# Remove all nodes with zero throughput and all arcs incident to at least one of these nodes. | |||
# Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum throughput <math>T(v_0)</math>. | # Let <math>v_0\in V\setminus\{s,t\}</math> be a node with minimum throughput <math>T(v_0)</math>. | ||
# Set <math>F(v_0):=T(v_0)</math> and <math> | # Set <math>F(v_0):=T(v_0)</math> and <math>F(v):=0</math> for all nodes <math>v\in V\setminus\{s,t,v_0\}</math>. | ||
# Run a modified [[Breadth-first search|BFS]] from <math>v_0</math>, where for every processed arc <math>(v,w)\in A</math>: | # Run a modified [[Breadth-first search|BFS]] from <math>v_0</math>, where for every processed arc <math>(v,w)\in A</math>: | ||
## Let <math>\Delta:=\min\{u(v,w),F(v)\}</math>. | ## Let <math>\Delta:=\min\{u(v,w),F(v)\}</math>. | ||
## | ## Set the flow over <math>(v,w)</math> to <math>\Delta</math>. | ||
## Increase <math>F(w)</math> by <math>\Delta</math>. | ## Increase <math>F(w)</math> by <math>\Delta</math>. | ||
## Decrease <math>F(v)</math> and <math> | ## Decrease <math>F(v)</math>, <math>T(v)</math>, and <math>u(v,w)</math> by <math>\Delta</math>. | ||
## If <math> | ## If <math>u(v,w)=0</math>, remove <math>(v,w)</math> from <math>G</math>. | ||
# Run | ## If <math>F(v)=0</math>, finish this iteration. | ||
# Run steps 4+5 from <math>v_0</math> on the [[Basic graph definitions#Transpose of a graph|transpose]] of <math>G</math> with the value of <math>T(v_0)</math> as computed in step 1 (all removals apply to <math>G</math>). | |||
'''Proof:''' | |||
Consider step 5 (step 6 is analogous). The specific choice of <matH>v_0</math> ensures <math>F(v)\leq T(v_0)\leq T(v)</math> for each node <math>v\in V</math> at any time. Therefore, all flow arrived at <math>v</math> can be moved forward along the arcs leaving <math>v</math>. In other words, when <math>v</math> is finished, it is <math>F(v)=0</math>. Since <math>G</math> is an [[Basic graph definitions#Cycles|<math>(s,t)</math>-graph]], the result is a feasible <math>(s,t)</math>-flow, and the flow value has increased by the initial value of <math>T(v_0)</math>. In particular, it is <math>T(v_0)=0</math> at the end, so at least <math>v_0</math> will be removed in this iteration. | |||
== Correctness == | |||
When a node is removed, either all of its outgoing arcs or all of its ingoing arcs are saturated. Therefore, an arc is only removed if this arc itself or all immediate predecessors or all immediate successors are saturated. In particular, an arc is only removed if it is not on any flow-augmenting path anymore. Therefore, when the break condition is fulfilled, the flow is blocking. Termination follows from the following complexity considerations. | |||
== Complexity == | |||
'''Statement:''' | |||
The asymptotic complexity is in <math>\mathcal{O}(n^2)</math>, where <math>n=|V|</math>. | |||
'''Proof:''' | '''Proof:''' | ||
Due to the variant, the number of iterations is linear in <math>n</math>. When an arc is saturated, it is removed in step 5.5 (resp., 6.5), so the total number of saturating increases of flow values of arcs over all iterations of the main loop is linear in the number of arcs, which is in <math>\mathcal{O}(n^2)</math>. In each execution of step 5 (resp., step 6), the flow on at most one outgoing (resp., incoming) arc of each node is increased without saturation, so the number of ''non''-saturating flow value settings is linear in the number of nodes in each iteration. | |||
== Remarks == | == Remarks == | ||
# The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari. | # The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari. | ||
# Of course, the nodes and arcs need not really be removed from the graph. However, "removed" nodes and arcs must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean | # Of course, the nodes and arcs need not really be removed from the graph. However, "removed" nodes and arcs must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean label "is removed" does not suffice for that. | ||
# This application of [[Breadth-first search|BFS]] is an example for one of the remarks on [[Graph traversal#Remarks|graph traversal]]: It is reasonable to implement graph-traversal algorithms as iterators. In fact, then the modification may be simply added to the loop that runs the iterator. | |||
Latest revision as of 11:27, 16 March 2017
General information
Algorithmic problem: Blocking flow.
Type of algorithm: loop.
Abstract view
Invariant: The current flow is feasible.
Variant: The number of nodes strictly decreases.
Break condition: There is no more ordinary [math]\displaystyle{ (s,t) }[/math]-path in [math]\displaystyle{ G }[/math].
Induction basis
Abstract view: The flow is initialized to be feasible, for example, the zero flow.
Proof: Obvious.
Induction step
Abstract view: Choose the node [math]\displaystyle{ v_0 }[/math] through which the minimum amount of flow may go, and propagate this amount from [math]\displaystyle{ v_0 }[/math] forward to [math]\displaystyle{ t }[/math] and backward to [math]\displaystyle{ s }[/math].
Implementation:
- For each node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math], let [math]\displaystyle{ T(v) }[/math] denote the throughput of [math]\displaystyle{ v }[/math], which is defined by [math]\displaystyle{ T(v):=\min\left\{\sum_{w:(v,w)\in A}u(v,w),\sum_{w:(w,v)\in A}u(w,v)\right\} }[/math].
- Remove all nodes with zero throughput and all arcs incident to at least one of these nodes.
- Let [math]\displaystyle{ v_0\in V\setminus\{s,t\} }[/math] be a node with minimum throughput [math]\displaystyle{ T(v_0) }[/math].
- Set [math]\displaystyle{ F(v_0):=T(v_0) }[/math] and [math]\displaystyle{ F(v):=0 }[/math] for all nodes [math]\displaystyle{ v\in V\setminus\{s,t,v_0\} }[/math].
- Run a modified BFS from [math]\displaystyle{ v_0 }[/math], where for every processed arc [math]\displaystyle{ (v,w)\in A }[/math]:
- Let [math]\displaystyle{ \Delta:=\min\{u(v,w),F(v)\} }[/math].
- Set the flow over [math]\displaystyle{ (v,w) }[/math] to [math]\displaystyle{ \Delta }[/math].
- Increase [math]\displaystyle{ F(w) }[/math] by [math]\displaystyle{ \Delta }[/math].
- Decrease [math]\displaystyle{ F(v) }[/math], [math]\displaystyle{ T(v) }[/math], and [math]\displaystyle{ u(v,w) }[/math] by [math]\displaystyle{ \Delta }[/math].
- If [math]\displaystyle{ u(v,w)=0 }[/math], remove [math]\displaystyle{ (v,w) }[/math] from [math]\displaystyle{ G }[/math].
- If [math]\displaystyle{ F(v)=0 }[/math], finish this iteration.
- Run steps 4+5 from [math]\displaystyle{ v_0 }[/math] on the transpose of [math]\displaystyle{ G }[/math] with the value of [math]\displaystyle{ T(v_0) }[/math] as computed in step 1 (all removals apply to [math]\displaystyle{ G }[/math]).
Proof: Consider step 5 (step 6 is analogous). The specific choice of [math]\displaystyle{ v_0 }[/math] ensures [math]\displaystyle{ F(v)\leq T(v_0)\leq T(v) }[/math] for each node [math]\displaystyle{ v\in V }[/math] at any time. Therefore, all flow arrived at [math]\displaystyle{ v }[/math] can be moved forward along the arcs leaving [math]\displaystyle{ v }[/math]. In other words, when [math]\displaystyle{ v }[/math] is finished, it is [math]\displaystyle{ F(v)=0 }[/math]. Since [math]\displaystyle{ G }[/math] is an [math]\displaystyle{ (s,t) }[/math]-graph, the result is a feasible [math]\displaystyle{ (s,t) }[/math]-flow, and the flow value has increased by the initial value of [math]\displaystyle{ T(v_0) }[/math]. In particular, it is [math]\displaystyle{ T(v_0)=0 }[/math] at the end, so at least [math]\displaystyle{ v_0 }[/math] will be removed in this iteration.
Correctness
When a node is removed, either all of its outgoing arcs or all of its ingoing arcs are saturated. Therefore, an arc is only removed if this arc itself or all immediate predecessors or all immediate successors are saturated. In particular, an arc is only removed if it is not on any flow-augmenting path anymore. Therefore, when the break condition is fulfilled, the flow is blocking. Termination follows from the following complexity considerations.
Complexity
Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math], where [math]\displaystyle{ n=|V| }[/math].
Proof: Due to the variant, the number of iterations is linear in [math]\displaystyle{ n }[/math]. When an arc is saturated, it is removed in step 5.5 (resp., 6.5), so the total number of saturating increases of flow values of arcs over all iterations of the main loop is linear in the number of arcs, which is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math]. In each execution of step 5 (resp., step 6), the flow on at most one outgoing (resp., incoming) arc of each node is increased without saturation, so the number of non-saturating flow value settings is linear in the number of nodes in each iteration.
Remarks
- The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari.
- Of course, the nodes and arcs need not really be removed from the graph. However, "removed" nodes and arcs must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean label "is removed" does not suffice for that.
- This application of BFS is an example for one of the remarks on graph traversal: It is reasonable to implement graph-traversal algorithms as iterators. In fact, then the modification may be simply added to the loop that runs the iterator.