Centroids,Representations, and Submodular Flows

The notion of centroid of a tree is generalized to apply to an arbitrary intersecting family of sets. Centroids are used to construct a compact representation for any intersecting family of sets, as well as any crossing family. The size of the representation for a family on n elements is O(n²), compared to size O(n³) for previous representations. Efficient algorithms to construct the representation are given. For example on a network of n vertices and m edges, the representation of all minimum cuts uses O(m log(n²/m)) space; it is constructed in O(nm log(n²/m)) time (this is the best-known time for finding one minimum cut). The representation is used to improve several submodular flow algorithms. For example a minimum-cost dijoin is found in time O(n²m); as a result a minimum-cost planar feedback are set is found in time O(n³). The previous best-known time bounds for these two problems are both a factor n larger.