Thek-Steiner Ratio in Graphs

A Steiner minimum tree (SMT) is the shortest-length tree in a metric space interconnecting a set of points, called the regular points, possibly using additional vertices. A k-size Steiner minimum tree (kSMT) is one that can be split into components where all regular points are leaves and all components have at most k leaves. The k-Steiner ratio, ρₖ, is the infimum of the ratios SMT/kSMT over all finite sets of regular points in all possible metric spaces, where the distances are given by a complete graph. Previously, only ρ₂ and ρ₃ were known exactly in graphs, and some bounds were known for other values of k. In this paper, we determine ρₖ exactly for all k. From this we prove a better approximation ratio for the Steiner tree problem in graphs.