<p>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. </p>

CC BY-SA 3.0
2014-07-24T21:24:43.357Z
2014-07-24T21:24:43.357Z
Chandra Chekuri
<p><a href="https://scholar.google.com/scholar?oi=bibs&amp;hl=en&amp;cluster=8044686711250386358" rel="nofollow noreferrer">The answer is yes</a>. There is a dynamic programming algorithm that runs in time <span class="math-container">$O^*(3^k)$</span>. It is a generalization of Dreyfus and Wagner's well-known algorithm for Steiner tree.</p>

CC BY-SA 4.0
2022-01-05T17:18:46.763Z
2022-01-05T17:18:46.763Z
Austin Buchanan
<p>Consider the node-weighted steiner problem:</p>
<blockquote>
<p>Input: a graph <span class="math-container">$G=(V,E)$</span>, a set <span class="math-container">$T\subseteq V$</span> of terminals, a weight function <span class="math-container">$w: V\setminus T \to \mathbb{R}_+$</span>.</p>
<p>Output: a minimum weight subset <span class="math-container">$S \subseteq V\setminus T$</span> of vertices such that <span class="math-container">$G[T\cup S]$</span> is connected.</p>
</blockquote>
<p>Is this problem polytime solvable when the number <span class="math-container">$|T|$</span> of terminals is a constant?</p>

CC BY-SA 4.0
2022-01-03T21:04:18.380Z
I was about to post this paper https://onlinelibrary.wiley.com/doi/10.1002/net.21825 as a further answer to your question, and then I realized that you are an author xD
Karagounis Z
<graph-algorithms><np-hardness><parameterized-complexity><fixed-parameter-tractable>
Node-weighted steiner problem with few terminals
Austin Buchanan
# Node-weighted steiner problem with few terminals

(Asked by: username_0 on 2014-07-24)

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?

**Tags:** graph-algorithms, np-hardness, parameterized-complexity, fixed-parameter-tractable
> **Comments:**
> **username_1**: I was about to post this paper https://onlinelibrary.wiley.com/doi/10.1002/net.21825 as a further answer to your question, and then I realized that you are an author xD  

---

## 2 answers

### Answer by username_2 on 2014-07-24. Score: 4 | Accepted answer

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.


---

### Answer by username_0 on 2022-01-05. Score: 0

[The answer is yes](https://scholar.google.com/scholar?oi=bibs&hl=en&cluster=8044686711250386358). 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.


---

