Cactus Representation of Minimum Cuts: Derandomize and Speed up

Given an undirected weighted graph with n vertices and m edges, we give the first deterministic m 1+o(1) -time algorithm for constructing the cactus representation of all global minimum cuts. This improves the current n 2+o(1) -time state-of-the-art deterministic algorithm, which can be obtained by combining ideas implicitly from three papers [Kar00, Li21, Gab16]. The known explicitly stated deterministic algorithm has a runtime of Õ(mn) [Fle99, NNI00]. Using our technique, we can even speed up the fastest randomized algorithm of [KP09] whose running time is at least Ω(m log 4 n) to O(m log 3 n).