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

• INSTANCE: Directed Graph $G=(V,E)$ , edge costs $w:E \rightarrow \mathbb{R}^+$ , root $r \in V$ , set of terminals $S \subset V$ of size $k \ge 2$ .
• SOLUTION: A directed tree $T=(V_{T}, E_{T})$ in $G$ rooted at $r$ such that $S \subseteq V_{T} \subseteq V$ and $T$ contains at most $p$ branching nodes
• COST FUNCTION: $\sum_{e \in E_{T}}c(e)$
• OBJECTIVE: Minimize.

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

• Comment: When both $k$ and $p$ are fixed, deciding existence of a feasible solution is in $P$ [106].