Minimum Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , edge costs $c: E \rightarrow \mathbb{R}^+$ , set of terminals $S\subseteq V$ .
• SOLUTION: A tree $T=(V_{T}, E_{T})$ in G such that $S \subseteq V_{T} \subseteq V$ , $E_{T} \subseteq E$ .
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$
• OBJECTIVE: Minimize.
• Approx.: Approximable within $\ln{4}+\epsilon < 1.39$ [21] (see also [98],[73]).
• Hardness: NP-hard to approximate within an approximation ratio 96/95 [36].
• Comment: Admits a PTAS in the special case when G is a planar graph [19]. Solvable exactly in time $O(3^kn+2^k(n\log n+m))$ , where $n=\vert V\vert$ is the number of vertices, $k=\vert S\vert$ the number of terminals and $m=\vert E\vert$ the number of edges in the graph [46],[68].