k-Bottleneck Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , edge costs $c: E \rightarrow \mathbb{R}^+$ , set of terminals $S\subseteq V$ , positive integer $k$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ in $G$ such that $S \subseteq V_{T} \subseteq V$ , $E_{T} \subseteq E$ and $\vert V_{T}\setminus S\vert \leq k$ (at most k Steiner nodes used).
• COST FUNCTION: $$\max_{e \in E_{T}}c(e)$$
• OBJECTIVE: Minimize.
• Hardness: NP-Hard to approximate within approximation ratio $2-\epsilon$ on undirected metric graphs [2]. NP-Hard to approximate within approximation ratio $\sqrt{2}-\epsilon$ in the Euclidean plane [103].
• Approx.: Approximable within approximation ratio $2$ on undirected metric graphs [2]. Approximable within approximation ratio $1.866$ in the Euclidean plane [105].
• Comment: For the euclidean case, exact algorithms exist for $k = 1$ and $k = 2$ , with time complexity $O(n \; log \; n)$ and $O(n^2)$ respectively [8]. For the special case of the euclidean plane with no edges allowed between two Steiner points, a $\sqrt{2}+ \epsilon$ approximation algorithm exists [85].