  The minimum cut problem for an undirected edge-weighted graph asks us to
divide its set of nodes into two blocks while minimizing the weight sum of the
cut edges. In this paper, we engineer the fastest known exact algorithm for the
problem.
  State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the
algorithm of Nagamochi, Ono and Ibaraki identify edges that can be contracted
to reduce the graph size such that at least one minimum cut is maintained in
the contracted graph. Our algorithm achieves improvements in running time over
these algorithms by a multitude of techniques. First, we use a recently
developed fast and parallel \emph{inexact} minimum cut algorithm to obtain a
better bound for the problem. Then we use reductions that depend on this bound,
to reduce the size of the graph much faster than previously possible. We use
improved data structures to further improve the running time of our algorithm.
Additionally, we parallelize the contraction routines of Nagamochi, Ono and
Ibaraki. Overall, we arrive at a system that outperforms the fastest
state-of-the-art solvers for the \emph{exact} minimum cut problem
significantly.
