ε -Dense Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , set of terminals $S\subseteq V$ such that each $s\in S$ has at least $\epsilon\cdot \vert V\setminus S\vert$ neighbors in $V\setminus S$
• SOLUTION: A Steiner tree $T = (V_T, E_T)$ for $S$ in $G$
• COST FUNCTION: length $\vert E_T\vert$ of $T$
• OBJECTIVE: Minimize
• Approx.: For every $\epsilon >0$ , there exists a PTAS for the $\epsilon$ -Dense Steiner Tree Problem [74]. This also yields existence of an efficient PTAS [64]). The $\Psi (n)$ -Subdense Steiner Tree Problem where every terminal has at least $\vert V\setminus S\vert\slash\Psi (n)$ non-terminal neighbors also admits a PTAS for $\Psi (n)=O(\log (n))$ [25].
• Comment: So far the problem is not known to be NP-hard in the exact setting.