Split and join: strong partitions and Universal Steiner trees for graphs

Abstract

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph G and a root node r, we seek a single spanning tree T of minimum stretch, where the stretch of T is defined to be the maximum ratio, over all subsets of terminals X, of the ratio of the cost of the sub-tree T_X that connects r to X to the cost of an optimal Steiner tree connecting X to r. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. We provide a polynomial time UST construction for general graphs with 2^O(√log n)-stretch. We also give a polynomial time polylogarithmic-stretch construction for minor-free graphs. One basic building block in our algorithm is a hierarchy of graph partitions, each of which guarantees small strong cluster diameter and bounded local neighbourhood intersections. Our partition hierarchy for minor-free graphs is based on the solution to a cluster aggregation problem that may be of independent interest. To our knowledge, this is the first sub-linear UST result for general graphs, and the first polylogarithmic construction for minor-free graphs.