The details of the paper are way over my head, but here's what I took away from a quick skim. The random sampling technique of Benzur and Karger approximately

The details of the paper are way over my head, but here's what I took away from a quick skim. The random sampling technique of Benzur and Karger approximately preserves the total weights of all cuts in the graph, up to certain error bounds (with high probability). That is, if you draw a particular cut through the graph, the original version might have 100 edges crossing the cut, and the sparse graph might have 3 edges crossing the cut with a total weight of 102. Since all cut sizes are approximately preserved, you can get an approximate answer to the min cut in the original graph by solving the same problem on the sparse graph. The deterministic, exact approach is a lot more complicated. In this case, we're not trying to preserve all cut weights, just the weights of minimum cuts. If you imagine a graph that consists of some dense "clusters" connected by other sparse "bottlenecks", then a minimum cut must go through the bottlenecks while avoiding the clusters. So hand-waving the details, if you could exactly partition the graph into dense clusters, you could just collapse each cluster into a single vertex, and then easily solve the min-cut problem on the graph of clusters instead of the original graph. This partitioning is hard to do exactly. But if you start by doing it approximately, then you can bound the number of "adjustments" that need to be made in order to make the partitioning work.