Group Steiner Tree Problem

• INSTANCE: Graph $G=(V,E)$ , edge cost $c: E \rightarrow \mathbb{R}^+$ , and sets $S_{1},..., S_{n} \subseteq V$ , also called groups.
• SOLUTION: A tree $T = (V_T, E_T)$ in $G$ which contains at least one terminal from every group $S_i$
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$ .
• OBJECTIVE: Minimize.
• Approx.: Approximable within $O(\log^{3}n)$ . Approximable within $O(\log^{2}n)$ if $G$ is a tree [53], [40].
• Hardness: Not approximable within $\Omega(\log^{2\textbf{-}\epsilon}n)$ unless NP admits quasipolynomial-time Las Vegas algorithm [61].
• Comment: Approximable within $O(\log n polylog \log n)$ when the graph is planar and each group is the set of nodes on a face [40].