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_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):=\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]).
- 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{ T(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].
- Increase the flow over [math]\displaystyle{ (v,w) }[/math] by [math]\displaystyle{ \Delta }[/math].
- Increase [math]\displaystyle{ F(w) }[/math] by [math]\displaystyle{ \Delta }[/math].
- Decrease [math]\displaystyle{ F(v) }[/math] and [math]\displaystyle{ T(v) }[/math] by [math]\displaystyle{ \Delta }[/math].
- If [math]\displaystyle{ T(v)=0 }[/math], remove [math]\displaystyle{ v }[/math] and all of its incident arcs from [math]\displaystyle{ G }[/math].
- 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) }[/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 }[/math] at the end, so at least [math]\displaystyle{ v_0 }[/math] will be removed in this 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 lable "is removed" does not suffice for that.