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.

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_ }[/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 potential [math]\displaystyle{ P(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\} }[/math].
4. Run a modified BFS from [math]\displaystyle{ v }[/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] by [math]\displaystyle{ \Delta }[/math].
   5. If [math]\displaystyle{ F(v)=0 }[/math], remove [math]\displaystyle{ v }[/math] and all of its incident arcs.
5. Run the same modification from [math]\displaystyle{ v_0 }[/math] on the transpose of the graph.

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 need not really be removed from the graph. However, "removed" nodes must be hidden from the algorithm to ensure the asymptotic complexity; a Boolean lable "is removed" does not suffice for that.