(MIN-CUT) MINIMUM CAPACITY (s,t) CUT *
Instance: Digraph G=(V,E), a pair of vertices s,t in V.
For each e=(x,y) in E a capacity C(e(x,y))>=0,
and C(e(y,x))>=0 (This is needed for our approach);
For all other pairs the capacity is 0.
Solution: A subset S of V containing s and not t.
Measure : C(S:V-S) (i.e. Sum {C(x,y): x in S and y is not)
+-------------------------------------------------------+
| The "Local-Ratio Theorem" (oriented for MIN-CUT) |
+-------------------------------------------------------+
| If S is MIN-CUT w.r.t the capacity function C1 |
| and S is MIN-CUT w.r.t the capacity function C2 |
| then S is MIN-CUT w.r.t the capacity function C1+C2 |
+-------------------------------------------------------+
Let (s=) x1,x2,...,xi,xi+1 (=t) and epsilon >0 where:
epsilon = Min{C(s,x2),C(x2,x3), ... , C(xi,t)}
(if non then the mincut value is 0! why?)
define C1(xj, xj+1) = +epsilon for j=1,2,...,i
and C1(xj+1,xj ) = -epsilon for j=1,2,...,i
and 0 otherwize
Q1: All s,t-cuts have the same C1's capacity. Why?
The algorithm: iteratively subtract C1 as above.
Induction hyp. implies that reclusive call with C2=C-C1
would return a set S which is MIN-CUT w.r.t. C2.
S (and any s,t cut) is MIN-CUT w.r.t. C1 (see Q1).
By the "Local-Ratio Theorem" S is MIN-CUT w.r.t. C=C1+C2.
Q2: What to do when no epsilon>0 path exists?
Q3: The above approach provide a partial correctness
for all augmenting path algorithms, like Ford and Dinitz. Why?
Comment: Can we use the Local-Ratio approach for non
augmenting path algorithms, like Goldbergs'?
It seems we* can. We hope to add it soon.
--------------------
* This page is an outcome of a work done with my student Dror Rawitz