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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.