Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
Abstract
In 1996, Karger \cite{KargerStoc} gave a startling randomized algorithm that finds a
minimum-cut in a (weighted) graph in time $O(m\log^3n)$ which he
termed near-linear time meaning linear (in the size of the input) times a polylogarthmic
factor. In this paper, we give the first deterministic algorithm
which runs in near-linear time for weighted graphs.
Previously, the breakthrough results of Kawarabayashi and Thorup \cite{KawarabayashiT19}
gave a near-linear time algorithm for simple graphs (which was
improved to have running time $O(m \log^2 n \log \log n)$ in
\cite{DBLP:journals/siamcomp/HenzingerRW20}.) The main technique here is a clustering procedure that
perfectly preserves minimum cuts. Recently, Li \cite{Li21} gave an
$m^{1+o(1)}$ deterministic minimum-cut algorithm for weighted graphs;
this form of running time has been termed ``almost-linear''. Li
uses almost-linear time deterministic expander decompositions which
do not perfectly preserve minimum cuts, but he can use these
clusterings to, in a sense, ``derandomize'' the methods of Karger.
In terms of techniques, we provide a structural theorem that says there
exists a sparse clustering that preserves minimum cuts in a weighted
graph with $o(1)$ error. In addition, we construct it
deterministically in near linear time. This was done exactly for
simple graphs in \cite{KawarabayashiT19,DBLP:journals/siamcomp/HenzingerRW20} and with polylogarithmic error for
weighted graphs in \cite{Li21}. Extending the
techniques in
\cite{KawarabayashiT19,DBLP:journals/siamcomp/HenzingerRW20} to
weighted graphs presents significant challenges,
and moreover, the algorithm can
only polylogarithmically approximately preserve minimum cuts. A
remaining challenge is to reduce the polylogarithmic-approximate
clusterings to $1+o(1/\log n)$-approximate so that they can be
applied recursively as in~\cite{Li21}
over $O(\log n)$ many levels.
This is an additional challenge that requires building on
properties of tree-packings in the presence of a wide range of edge
weights to, for example, find sources for local flow computations
which identify minimum cuts that cross clusters.
minimum-cut in a (weighted) graph in time $O(m\log^3n)$ which he
termed near-linear time meaning linear (in the size of the input) times a polylogarthmic
factor. In this paper, we give the first deterministic algorithm
which runs in near-linear time for weighted graphs.
Previously, the breakthrough results of Kawarabayashi and Thorup \cite{KawarabayashiT19}
gave a near-linear time algorithm for simple graphs (which was
improved to have running time $O(m \log^2 n \log \log n)$ in
\cite{DBLP:journals/siamcomp/HenzingerRW20}.) The main technique here is a clustering procedure that
perfectly preserves minimum cuts. Recently, Li \cite{Li21} gave an
$m^{1+o(1)}$ deterministic minimum-cut algorithm for weighted graphs;
this form of running time has been termed ``almost-linear''. Li
uses almost-linear time deterministic expander decompositions which
do not perfectly preserve minimum cuts, but he can use these
clusterings to, in a sense, ``derandomize'' the methods of Karger.
In terms of techniques, we provide a structural theorem that says there
exists a sparse clustering that preserves minimum cuts in a weighted
graph with $o(1)$ error. In addition, we construct it
deterministically in near linear time. This was done exactly for
simple graphs in \cite{KawarabayashiT19,DBLP:journals/siamcomp/HenzingerRW20} and with polylogarithmic error for
weighted graphs in \cite{Li21}. Extending the
techniques in
\cite{KawarabayashiT19,DBLP:journals/siamcomp/HenzingerRW20} to
weighted graphs presents significant challenges,
and moreover, the algorithm can
only polylogarithmically approximately preserve minimum cuts. A
remaining challenge is to reduce the polylogarithmic-approximate
clusterings to $1+o(1/\log n)$-approximate so that they can be
applied recursively as in~\cite{Li21}
over $O(\log n)$ many levels.
This is an additional challenge that requires building on
properties of tree-packings in the presence of a wide range of edge
weights to, for example, find sources for local flow computations
which identify minimum cuts that cross clusters.
