The Steiner Tree problem is a classical problem in combinatorial optimization: the goal is to connect a set $T$ of terminals in a graph $G$ by a tree of minimum size. Karpinski and Zelikovsky (1996) studied the $delta$-dense version of {sc Steiner Tree}, where each terminal has at least $delta |V(G)setminus T|$ neighbours outside $T$, for a fixed $delta > 0$. They gave a PTAS for this problem. We study a generalization of pairwise $delta$-dense {sc Steiner Forest}, which asks for a minimum-size forest in $G$ in which the nodes in each terminal set $T_1,dots,T_k$ are connected, and every terminal in $T_i$ has at least $delta |T_j|$ neighbours in $T_j$, and at least $delta|S|$ nodes in $S = V(G)setminus (T_1cupdotscup T_k)$, for each $i, j$ in ${1,dots, k}$ with $i eq j$. Our first result is a polynomial-time approximation scheme for all $delta > 1/2$. Then, we show a $(frac{13}{12}+varepsilon)$-approximation algorithm for $delta = 1/2$ and any $varepsilon > 0$. We also consider the $delta$-dense Group Steiner Tree problem as defined by Hauptmann and show that the problem is $mathsf{APX}$-hard.
Download