  A cut sparsifier is a reweighted subgraph that maintains the weights of the
cuts of the original graph up to a multiplicative factor of $(1\pm\epsilon)$.
This paper considers computing cut sparsifiers of weighted graphs of size
$O(n\log (n)/\epsilon^2)$. Our algorithm computes such a sparsifier in time
$O(m\cdot\min(\alpha(n)\log(m/n),\log (n)))$, both for graphs with polynomially
bounded and unbounded integer weights, where $\alpha(\cdot)$ is the functional
inverse of Ackermann's function. This improves upon the state of the art by
Bencz\'ur and Karger (SICOMP 2015), which takes $O(m\log^2 (n))$ time. For
unbounded weights, this directly gives the best known result for cut
sparsification. Together with preprocessing by an algorithm of Fung et al.
(SICOMP 2019), this also gives the best known result for polynomially-weighted
graphs. Consequently, this implies the fastest approximate min-cut algorithm,
both for graphs with polynomial and unbounded weights. In particular, we show
that it is possible to adapt the state of the art algorithm of Fung et al. for
unweighted graphs to weighted graphs, by letting the partial maximum spanning
forest (MSF) packing take the place of the Nagamochi-Ibaraki (NI) forest
packing. MSF packings have previously been used by Abraham at al. (FOCS 2016)
in the dynamic setting, and are defined as follows: an $M$-partial MSF packing
of $G$ is a set $\mathcal{F}=\{F_1, \dots, F_M\}$, where $F_i$ is a maximum
spanning forest in $G\setminus \bigcup_{j=1}^{i-1}F_j$. Our method for
computing (a sufficient estimation of) the MSF packing is the bottleneck in the
running time of our sparsification algorithm.
