### Question

In the *node-weighted Steiner tree problem*, we are given as input an undirected graph $G = (V, E)$, node weights $w_i \geq 0$ for all $i \in V$, edge costs $c_e \geq 0$ for all $e \in E$, and a set of terminals $T \subseteq V$. The cost of a tree is the sum of the weights of the nodes plus the sum of the costs of the edges in the tree. The goal of the problem is to find a minimum-weight tree that spans all the terminals in $T$.

- Show that there exists some $c$ such that there is no $(c \ln T)$-approximation algorithm for the node-weighted Steiner tree problem unless P = NP.
- Give a greedy $O(\ln T)$-approximation algorithm for the node-weighted Steiner tree problem.

### Answers

**1.** We show an approximation preserving reduction from set cover. Let $(U, \mathcal{S})$ be an instance of the set cover problem and define the node-weighted Steiner tree instance $(G, T, w)$ where $G = (\{r\} \cup \mathcal{S} \cup U, E)$, $E = \{r\} \times \mathcal{S} \cup \{(i, j) : i \in S_j\}$ and for each $S_j \in \mathcal{S}$ set $w(S_j)$ to be 1 and 0 otherwise (both edges and vertices).

One can verify that any solution to the Steiner tree instance can be transformed to a solution to the set cover instance of the same cost and vice versa.

**2.** We describe an iterative algorithm that in each iteration contract an induced subgraph of $G$ that contains at least two terminals. The induced subgraph to contract is a spider that minimizes the cost of the subgraph per terminal it contains. A spider is a tree whose leafs are terminals and all vertices have degree two beside the leafs and, possibly, another vertex. We can assume w.l.o.g that the weights of the terminals are zero, and observe that any Steiner tree can be decomposed into spiders, thus, in any iteration, the cost we pay per terminal is at most $\frac{OPT}{T_i}$, where $T_i$ is the number of terminals left at the beginning of the $i$th iteration. The total cost, then, is no more than $\sum_{i = 1}^|T| \frac{OPT}{i} \leq H_T OPT\leq O(\ln T)OPT$.