An NC Algorithm for Minimum Cuts
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$.