Derandomization through Approximation: An NC Algorithm for Minimum Cuts

摘要

The authors prove that the minimum cut problem can be solved in NC on arbitrarilyweighted undirected graphs. They do so by giving three separate and independently interesting results. The first is a relatively straighforward NC (2+epsilon)-approximation algorithm for the minimum cut. It uses O(m2/n) processors. The second result is a randomized reduction of the minimum cut problem to the minimum cut approximation problem. The third is a derandomization of this reduction. Performing the derandomization requires a novel combination of two previously known derandomization techniques: pairwise independence and random walks on expanders.