Minimum cuts in near-linear time
We significantly improve known time bounds for solving the minimum cut problem on undirected graphs.  We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an <italic>m</italic>-edge, <italic>n</italic>-vertex graph with high probability in <italic>O</italic>(m log<supscrpt>3</supscrpt>  <italic>n</italic>) time. We also give a simpler randomized algorithm that finds <italic>all</italic> minimum cuts with high probability in O(<italic>m</italic> log<supscrpt>3</subscrpt> <italic>n</italic>) time. This variant has an optimal <italic>RNC</italic> parallelization.  Both variants improve on the previous best time bound of <italic>O<italic>(<italic>n<italic><supscrpt>2</supscrpt> log<supscrpt>3</supscrpt> <italic>n<italic>). Other applications of the tree-packing approach are new, nearly tight bounds on the number of <italic>near-minimum</italic> cuts a graph may have and a new data structure for representing them in a space-efficient manner.