Question

steiner_tree

In the node-weighted Steiner tree problem, we are given as input an undirected graph G=(V,E)G = (V, E), node weights wi0w_i \geq 0 for all iVi \in V, edge costs ce0c_e \geq 0 for all eEe \in E, and a set of terminals TVT \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 TT.

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

Answers

1. We show an approximation preserving reduction from set cover. Let (U,S)(U, \mathcal{S}) be an instance of the set cover problem and define the node-weighted Steiner tree instance (G,T,w)(G, T, w) where G=({r}SU,E)G = (\{r\} \cup \mathcal{S} \cup U, E), E={r}×S{(i,j):iSj}E = \{r\} \times \mathcal{S} \cup \{(i, j) : i \in S_j\} and for each SjSS_j \in \mathcal{S} set w(Sj)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 GG 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 OPTTi\frac{OPT}{T_i}, where TiT_i is the number of terminals left at the beginning of the iith iteration. The total cost, then, is no more than i=1TOPTiHTOPTO(lnT)OPT\sum_{i = 1}^|T| \frac{OPT}{i} \leq H_T OPT\leq O(\ln T)OPT.

1
Feedback