Minimum-Cost ($k,p$ )-Steiner Tree with Limited Number of Branching Nodes

• INSTANCE: Graph $G=(V,E)$ , edge costs $c: E \rightarrow \mathbb{R}^+$ , a set $S \subset V$ of $k$ terminals.
• SOLUTION: A Steiner tree $T=(V_{T}, E_{T})$ for $S$ in $G$ such that $T$ contains at most $p$ branching nodes.
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$
• OBJECTIVE: Minimize.
• Approx.: For $p$ being constant, solvable in polynomial time when the input graph is acyclic or when $k$ is also fixed and the input graph is of bounded treewidth [106]

• Hardness: NP-hard to approximate within $n^{1\mbox{-}\epsilon}$ for every $\epsilon >0$ when $k$ is not fixed, even in planar graphs with unit edge costs [106]