Abstract:

We give a deterministic min-cut algorithm for weighted undirected graphs

that runs in time $m^{1+\epsilon}$ plus polylog$(n)$ max-flow

computations. Using the current best max-flow algorithms, this results

in an overall running time of $\tilde O(m \cdot \min(\sqrt{m},n^{2/3}))$

for weighted graphs, and $m^{4/3+o(1)}$ for unweighted

(multi)-graphs. This is the first improvement in the running time of

deterministic algorithms for the min-cut problem on weighted graphs and

unweighted multi-graphs since the early 1990s when a running time bound

of $\tilde O(mn)$ was established for this problem. A key component in our

algorithm is the use of deterministic expander decompositions.

Conceptually, this allows us to build on, and generalize, the recent

breakthrough for this problem by Kawarabayashi and Thorup (STOC 2015)

who obtained a running time of $\tilde O(m)$ for $\textit{simple graphs}$.

Although our running time is larger, our algorithm is more general in

that it can handle edge weights and/or parallel edges. Our result makes

progress toward closing the gap between the randomized and deterministic

runtimes for the min-cut problem on general weighted graphs that has

existed for over 20 years.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.