(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