A Nearly Optimal All-Pairs Min-Cuts Algorithm in Simple Graphs
Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak · 2022
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$.