  We study the problem of computing the minimum cut in a weighted distributed
message-passing networks (the CONGEST model). Let $\lambda$ be the minimum cut,
$n$ be the number of nodes in the network, and $D$ be the network diameter. Our
algorithm can compute $\lambda$ exactly in $O((\sqrt{n} \log^{*} n+D)\lambda^4
\log^2 n)$ time. To the best of our knowledge, this is the first paper that
explicitly studies computing the exact minimum cut in the distributed setting.
Previously, non-trivial sublinear time algorithms for this problem are known
only for unweighted graphs when $\lambda\leq 3$ due to Pritchard and
Thurimella's $O(D)$-time and $O(D+n^{1/2}\log^* n)$-time algorithms for
computing $2$-edge-connected and $3$-edge-connected components.
  By using the edge sampling technique of Karger's, we can convert this
algorithm into a $(1+\epsilon)$-approximation $O((\sqrt{n}\log^{*}
n+D)\epsilon^{-5}\log^3 n)$-time algorithm for any $\epsilon>0$. This improves
over the previous $(2+\epsilon)$-approximation $O((\sqrt{n}\log^{*}
n+D)\epsilon^{-5}\log^2 n\log\log n)$-time algorithm and
$O(\epsilon^{-1})$-approximation $O(D+n^{\frac{1}{2}+\epsilon}
\mathrm{poly}\log n)$-time algorithm of Ghaffari and Kuhn. Due to the lower
bound of $\Omega(D+n^{1/2}/\log n)$ by Das Sarma et al. which holds for any
approximation algorithm, this running time is tight up to a $ \mathrm{poly}\log
n$ factor.
  To get the stated running time, we developed an approximation algorithm which
combines the ideas of Thorup's algorithm and Matula's contraction algorithm. It
saves an $\epsilon^{-9}\log^{7} n$ factor as compared to applying Thorup's tree
packing theorem directly. Then, we combine Kutten and Peleg's tree partitioning
algorithm and Karger's dynamic programming to achieve an efficient distributed
algorithm that finds the minimum cut when we are given a spanning tree that
crosses the minimum cut exactly once.
