Approximating Steiner Trees and Forests with Minimum Number of Steiner Points

Abstract. Let R be a finite set of terminals in a metric space (M,d). We consider finding a minimum size set S ⊆M of additional points such that the unit-disc graph G[R ∪ S] of R ∪ S satisfies some connectivity properties. In the Steiner Tree with Minimum Number of Steiner Points (ST-MSP) problem G[R ∪ S] should be connected. In the more general Steiner Forest with Minimum Number of Steiner Points (SF-MSP) problem we are given a set D ⊆ R × R of demand pairs and G[R ∪ S] should contains a uv-path for every uv ∈ D. Let ∆ be the maximum number of points in a unit ball such that the distance between any two of them is larger than 1. It is known that ∆ = 5 in R2. The previous known approx-imation ratio for ST-MSP was ⌊(∆+1)/2⌋+1+ǫ in an arbitrary normed space [15], and 2.5+ ǫ in the Euclidean space R2 [5]. Our approximation ratio for ST-MSP is 1+ln(∆−1)+ǫ in an arbitrary normed space, which in R2 reduces to 1+ln 4+ǫ < 2.3863+ǫ. For SF-MSP we give a simple ∆-approximation algorithm, improving the folklore ratio 2(∆ − 1). Finally, we generalize and simplify the ∆-approximation of Calinescu [3] for the 2-Connectivity-MSP problem, where G[R ∪ S] should be 2-connected.