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 \subseteq M$ of additional points such that the unit-disc graph $G[R \cup S]$ of $R \cup S$ satisfies some connectivity properties. In the Steiner Tree with Minimum Number of Steiner Points (ST-MSP) problem $G[R \cup 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 \subseteq R \times R$ of demand pairs and $G[R \cup S]$ should contains a $uv$-path for every $uv \in D$. Let $\varDelta$ 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 $\varDelta =5$ in $\mathbb {R}^2$. The previous known approximation ratio for ST-MSP was $\lfloor (\varDelta +1)/2 \rfloor +1+\epsilon$ in an arbitrary normed space [15], and $2.5+\epsilon$ in the Euclidean space $\mathbb {R}^2$ [5]. Our approximation ratio for ST-MSP is $1+\ln (\varDelta -1)+\epsilon$ in an arbitrary normed space, which in $\mathbb {R}^2$ reduces to $1+\ln 4+\epsilon < 2.3863 +\epsilon$. For SF-MSP we give a simple $\varDelta$-approximation algorithm, improving the folklore ratio $2(\varDelta -1)$. Finally, we generalize and simplify the $\varDelta$-approximation of Calinescu [3] for the $2$ -Connectivity-MSP problem, where $G[R \cup S]$ should be $2$-connected.