<p>To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard).</p>
<p>In &quot;Parameterized Algorithms to Preserve Connectivity&quot; they show that a Cactus Augmentation Problem can be transformed into an equivalent Node-weighted Steiner Tree problem where each Steiner node is incident on exactly 2 terminals.</p>
<p>Hence, a polynomial time algorithm for my problem would imply a polynomial time algorithm for Cactus Augmentation which would mean P=NP.</p>

CC BY-SA 4.0
2021-10-06T18:40:49.967Z
"reduction to" -> "reduction from" :-)
Neal Young
CC BY-SA 4.0
2021-10-07T02:25:41.427Z
Thanks 
Karagounis Z
CC BY-SA 4.0
2021-10-06T17:57:49.117Z
2021-10-07T02:24:48.597Z
2021-10-07T02:24:48.597Z
Karagounis Z
<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>This problem is known to be at least as hard as Set Cover. However, I am interested in a more special case of node-weighted steiner tree, in which:</p>
<ol>
<li>Each steiner node is incident to exactly 2 terminals of <span class="math-container">$T$</span></li>
<li><span class="math-container">$T$</span> is an independent set.</li>
</ol>
<p>If I added a third condition that every pair of steiner nodes are adjacent, then this would be equivalent to an <em>edge cover</em> problem, which can be solved in polynomial time.</p>
<p>Hence, my special case lies somewhere in the middle between very hard to approximate (node weighted steiner tree), and exactly solvable (edge cover).</p>
<p>Since I don't know whether this is in P or NP-hard or to what extent it is approximable, any ideas about algorithms or hardness results on this problem would be welcome. Thanks!</p>

<graph-theory><graph-algorithms><np-hardness><approximation-algorithms>
Can this special case of Node Weighted Steiner Tree be solved in polynomial time?
Karagounis Z
# Can this special case of Node Weighted Steiner Tree be solved in polynomial time?

(Asked by: username_0 on 2021-10-02)

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.

This problem is known to be at least as hard as Set Cover. However, I am interested in a more special case of node-weighted steiner tree, in which:

1. Each steiner node is incident to exactly 2 terminals of $T$
2. $T$ is an independent set.

If I added a third condition that every pair of steiner nodes are adjacent, then this would be equivalent to an *edge cover* problem, which can be solved in polynomial time.

Hence, my special case lies somewhere in the middle between very hard to approximate (node weighted steiner tree), and exactly solvable (edge cover).

Since I don't know whether this is in P or NP-hard or to what extent it is approximable, any ideas about algorithms or hardness results on this problem would be welcome. Thanks!

**Tags:** graph-theory, graph-algorithms, np-hardness, approximation-algorithms


---

## 1 answers

### Answer by username_0 on 2021-10-06. Score: 3

To answer my own question, I have found that this problem is indeed NP-Hard via a reduction from the Cactus Augmentation Problem (which is NP-hard).

In "Parameterized Algorithms to Preserve Connectivity" they show that a Cactus Augmentation Problem can be transformed into an equivalent Node-weighted Steiner Tree problem where each Steiner node is incident on exactly 2 terminals.

Hence, a polynomial time algorithm for my problem would imply a polynomial time algorithm for Cactus Augmentation which would mean P=NP.

> **Comments:**
> **username_1**: "reduction to" -> "reduction from" :-)  
> **username_0**: Thanks   

---

