Differential approximation results for the Steiner tree problem Original Research Article

We study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than |V N−ϵ for any ϵ ϵ (0, 1), where V and N are the vertex-set of the input graph and the set of terminal vertices, respectively. For the second of the Steiner tree versions considered, the one where the input graph is supposed complete and the edge distances are arbitrary, we prove that it can be differentially approximated within View the MathML source. For the third one defined on complete graphs with edge distances 1 or 2, we show that it is differentially approximable within 0.82. Also, extending the result of Bern and Plassmann [1], we show that the Steiner tree problem with edge lengths 1 and 2 is MaxSNP-complete even in the case where IVY ⩽ rINI, for any r > 0. This allows us to finally show that the Steiner tree problem with edge lengths 1 and 2 cannot by approximated by polynomial time differential approximation schemata.