An (mn) Gomory-Hu tree construction algorithm for unweighted graphs

We present a fast algorithm for computing a Gomory-Hu tree or cut tree for an unweighted undirected graph G = (V,E). The expected running time of our algorithm is Õ(mc) where |E| = m and c is the maximum u-v edge connectivity, where u, v ? V . When the input graph is also simple (i.e., it has no parallel edges), then the u-v edge connectivity for each pair of vertices u and v is at most n-1; so the expected running time of our algorithm for simple unweighted graphs is Õ(mn). All the algorithms currently known for constructing a Gomory-Hu tree [8, 9] use n - 1 minimum s-t cut (i.e., max flow) subroutines. This in conjunction with the current fastest Õ (n20/9) max flow algorithm due to Karger and Levine[11] yields the current best running time of Õ(n20/9n) for Gomory-Hu tree construction on simple unweighted graphs with m edges and n vertices. Thus we present the first Õ (mn) algorithm for constructing a Gomory-Hu tree for simple unweighted graphs. We do not use a max flow subroutine here; we present an efficient tree packing algorithm for computing Steiner edge connectivity and use this algorithm as our main subroutine. The advantage in using a tree packing algorithm for constructing a Gomory-Hu tree is that the work done in computing a minimum Steiner cut for a Steiner set S ? V can be reused for computing a minimum Steiner cut for certain Steiner sets S ? S. Copyright 2007 ACM.