Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
