Subcubic algorithms for Gomory-Hu tree in unweighted graphs

Every undirected graph G has a (weighted) cut-equivalent tree T , commonly named after Gomory and Hu who discovered it in 1961. Both T and G have the same node set, and for every node pair s, t, the minimum (s, t)-cut in T is also an exact minimum (s, t)-cut in G. We give the first subcubic-time algorithm that constructs such a tree for a simple graph G (unweighted with no parallel edges). Its time complexity is Õ(n 2.5 ), for n = |V (G)|; previously, only Õ(n 3 ) was known, except for restricted cases like sparse graphs. Consequently, we obtain the first algorithm for All-Pairs Max-Flow in simple graphs that breaks the cubic-time barrier. Gomory and Hu compute this tree using n -1 queries to (single-pair) Max-Flow; the new algorithm can be viewed as a fine-grained reduction to Õ( √ n) Max-Flow computations on n-node graphs.