# Node-weighted steiner problem with few terminals

Consider the node-weighted steiner problem:

Input: a graph $$G=(V,E)$$, a set $$T\subseteq V$$ of terminals, a weight function $$w: V\setminus T \to \mathbb{R}_+$$.

Output: a minimum weight subset $$S \subseteq V\setminus T$$ of vertices such that $$G[T\cup S]$$ is connected.

Is this problem polytime solvable when the number $$|T|$$ of terminals is a constant?

An algorithm with a run-time of $n^{poly(k)}$ should be easy where $n = |V|$ and $k = |T|$. Think of an optimum solution which is edge-minimal. It will be a tree and one can see that the number of nodes with degree $\ge 3$ in this tree will be $O(k)$. We can guess those nodes $A$. Once we guess those nodes we create a graph on $A \cup T$ with edge-lengths between two nodes $u,v$ equal to the shortest node-weighted path between $u$ and $v$ in $G$ (we do not include the end points in this calculation). Then find a min-cost spanning tree in the resulting graph.
The answer is yes. There is a dynamic programming algorithm that runs in time $$O^*(3^k)$$. It is a generalization of Dreyfus and Wagner's well-known algorithm for Steiner tree.