Three indians' algorithm

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:

1. For each node [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math], let [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] (the throughput of node [math]\displaystyle{ v }[/math]).
2. Let [math]\displaystyle{ v_0\in V\setminus\{s,t\} }[/math] be a node with minimum throughput [math]\displaystyle{ T(v_0) }[/math].
3. Set [math]\displaystyle{ F(v_0):=T(v_0) }[/math] and [math]\displaystyle{ T(v):=0 }[/math] for all nodes [math]\displaystyle{ v\in V\setminus\{s,t,v_0\} }[/math].
4. Run a modified BFS from [math]\displaystyle{ v_0 }[/math], where for every processed arc [math]\displaystyle{ (v,w)\in A }[/math]:
   1. Let [math]\displaystyle{ \Delta:=\min\{u(v,w),F(v)\} }[/math].
   2. Increase the flow over [math]\displaystyle{ (v,w) }[/math] by [math]\displaystyle{ \Delta }[/math].
   3. Increase [math]\displaystyle{ F(w) }[/math] by [math]\displaystyle{ \Delta }[/math].
   4. Decrease [math]\displaystyle{ F(v) }[/math] and [math]\displaystyle{ T(v) }[/math] by [math]\displaystyle{ \Delta }[/math].
   5. If [math]\displaystyle{ (v,w) }[/math] is saturated, remove [math]\displaystyle{ (v,w) }[/math] from [math]\displaystyle{ G }[/math].
   6. If [math]\displaystyle{ T(v)=0 }[/math], remove [math]\displaystyle{ v }[/math] and all of its incident arcs from [math]\displaystyle{ G }[/math].
5. Run the same modified BFS from [math]\displaystyle{ v_0 }[/math] on the transpose of [math]\displaystyle{ G }[/math] (all removals apply to [math]\displaystyle{ G }[/math]).

Proof: Consider step 4 (step 5 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]. In summary, the result is a feasible [math]\displaystyle{ (s,t) }[/math]-flow again, and the flow valiue 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, the resulting flow is blocking.

Complexity

Statement: The asymptotic complexity is in [math]\displaystyle{ \mathcal{O}(n^2) }[/math], where [math]\displaystyle{ n=|V| }[/math].

Proof: The number of iterations is linear in [math]\displaystyle{ n }[/math]. When an arc is saturated, it is removed, 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 4 (resp., step 5), the flow on at most one outgoing (ingoing) arc of each node is increased without saturation, so the number of non-saturating increases is linear in the number of nodes in each iteration. Finally, when an arc is touched but no flow is sent over it, this arc is instantly removed, so the number of steps of this type is linear in the number of arcs as well.

Remarks

1. The algorithm is named after three indian researchers, V. M. Malhotra, M. Pramodh Kumar, and S. N. Mahashwari.
2. 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 lable "is removed" does not suffice for that.
3. 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.