A network-flow technique for finding low-weight bounded-degree spanning trees

Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low-weight spanning tree such that the degree of each vertex is at most its specified bound is considered. In particular, modifying a given spanning tree T using adoptions to meet the degree constraints is considered. A novel network-flow-based algorithm for finding a good sequence of adoptions is introduced. The method yields a better performance guarantee than any previous algorithm. If the degree constraint d(v) for each v is at least 2, the algorithm is guaranteed to find a tree whose weight is at most the weight of the given tree times 2 - min{(d(v) - 2)/(deg(T)(v) - 2):deg(T)(v) > 2}, where deg(T)(v) is the initial degree of v. Equally importantly, it takes this approach to the limit in the following sense: if any performance guarantee that is solely a function of the topology and edge weights of a given tree holds for any algorithm at all, then it also holds for the given algorithm. Examples are provided in which no lighter tree meeting the degree constraint exists. Linear-time algorithms are provided with the same worst-case performance guarantee. Choosing T to be a minimum spanning tree yields approximation algorithms with factors less than 2 for the general problem on geometric graphs with distances induced by various L-p norms. Finally, examples of Euclidean graphs are provided in which the ratio of the lengths of an optimal Traveling Salesman path and a minimum spanning tree can be arbitrarily close to 2. (C) 1997 Academic Press.