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 O(n^{ 2.75 }), for n=|V(G)|; previously, only O(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 O(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) .
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 O(n^{ 2.5 }), for n=|V(G)|; previously, only O(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 O(n) Max-Flow computations on n-node graphs .
R
st-cut
(s,t)-cut
R
st-cut
(s,t)-cut
R
an unweighted graph G
a simple graph G (unweighted with no parallel edges)
R
2.75
2.5
R
unweighted
simple
D
. 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)