An $\NC$ Algorithm for Minimum Cuts
David R. Karger, Rajeev Motwani · SIAM Journal on Computing · 1997
We show that the minimum-cut problem for weighted undirected graphs can be solved in $\NC$ using three separate and independently interesting results. The first is an $(m^2/n)$-processor $\NC$ algorithm for finding a $(2+\epsilon)$-approximation to the minimum cut. The second is a randomized reduction from the minimum-cut problem to the problem of obtaining a $(2+\epsilon)$-approximation to the minimum cut. This reduction involves a natural combinatorial set-isolation problem that can be solved easily in $\RNC$. The third result is a derandomization of this $\RNC$ solution that requires a combination of two widely used tools: pairwise independence and random walks on expanders. We believe that the set-isolation approach will prove useful in other derandomization problems. The techniques extend to two related problems: we describe $\NC$ algorithms finding minimum k-way cuts for any constant k and finding all cuts of value within any constant factor of the minimum. Another application of these techniques yields an $\NC$ algorithm for finding a {\em sparse k-connectivity certificate} for all polynomially bounded values of k. Previously, an $\NC$ construction was only known for polylogarithmic values of k.