A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs

We give an
$n^{2+o(1)}$
-time algorithm for finding
$s-t$
min-cuts for all pairs of vertices
$s$
and
$t$
in a simple, undirected graph on
$n$
vertices. We do so by constructing a Gomory-Hu tree (or cut equivalent tree) in the same running time, thereby improving on the recent bound of
$\tilde{O}(n^{2.5})$
by Abboud et al. (STOC 2021). Our running time is nearly optimal as a function of
$n$
.