MINIMUM STEINER TREE

• INSTANCE: Complete graph $G=\left(V,E\right)$, a metric given by edge weights $s: E\rightarrow N$ and a subset $S\subseteq V$ of required vertices.

• SOLUTION: A Steiner tree, i.e., a subtree of G that includes all the vertices in S.

• MEASURE: The sum of the weights of the edges in the subtree.

  
  

• Good News: Approximable within $1+(\ln 3)/2=1.55$ [424].

• Bad News: APX-complete [78].

• Comment: Variation in which the weights are only 1 or 2 is still APX-complete [78], but approximable within 1.28 [424]. When all weights lie in an interval $[\alpha,\alpha(1+1/k)]$ the problem is approximable within $1+1/ek+O(1/k^2)$ [231]. On directed graphs the problem is approximable within $O(\vert S\vert^\varepsilon )$ for any $\varepsilon >0$ [99].

  The variation in which the diameter of the tree is bounded by a constant d the problem is not approximable within $(1-\varepsilon )\ln \vert V\vert$ for any $\varepsilon >0$, unless NP $\subset\mbox{\sc Dtime}(n^{\log\log n})$, but approximable within $\log\vert V\vert$ for $d\in\{4,5\}$ [55] and within $d\log\vert V\vert$ for any constant $d\ge 6$ [335]. Admits a PTAS for the network Steiner tree problem if every element of S is adjacent to $\Theta(\vert V-S\vert)$ elements from V-S [297] and [294].

  A prize-collecting variation in which a penalty is associated with each vertex and the goal is to minimize the cost of the tree and the vertices in S not in the tree is approximable within $2-1/(\vert V\vert-1)$ [197]. The variation, called MINIMUM K-STEINER TREE, in which an integer $k \leq \vert S\vert$ is given in input and at least k vertices of S must be included in the subtree is approximable within 17 [86]. Variation in which all non-required vertices are pairwise nonadjacent is approximable within 1.28 [424]. Variation in which there are groups of required vertices and each group must be touched by the Steiner tree is approximable within $O(\log^3\vert V\vert\log g)$, where g is the number of groups [185]; when the number of groups is unbounded the problem is harder than MINIMUM DOMINATING SET to approximate, even if all edge weights are 1 [267].

  The constrained variation in which the input is extended with a positive integer k and a subset T of E, and the problem is to find the Steiner tree of weight at most k that contains the largest number of edges from T, is not approximable within $\vert E\vert^{\varepsilon }$ for some $\varepsilon >0$ [476]. If the solution is allowed to be a forest with at most q trees, for a given constant q, the problem is approximable within $2(1-1/(\vert S\vert-q+1))$ [417]. If the topology of the Steiner tree is given as input, the problem admits a PTAS [273]. Finally, if before computing the Steiner tree the graph can be modified by reducing the weight of the edges within a given budget the problem of looking for the best reduction strategy is APX-hard [138].

• Garey and Johnson: ND12