Subcubic Algorithms for Gomory-Hu Tree in Unweighted Graphs
share
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 st-cut in T is also an exact minimum st-cut in G. We give the first subcubic-time algorithm that constructs such a tree for an unweighted graph G. Its time complexity is Õ(n^2.75), 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 unweighted 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. Thus, under the assumption that Max-Flow can be computed in almost-linear time, our time bound improves further to n^2.5+o(1). Even under this assumption, no algorithm was previously known to be subcubic.
READ FULL TEXT