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.

Authors

• Amir Abboud
• Robert Krauthgamer
• Ohad Trabelsi

Keywords

• Gomory-Hu trees
• maximum flow
• minimum cut