On the terminal Steiner tree problem. (Q1853109)

We investigate a practical variant of the well-known graph Steiner tree problem. In this variant, every target vertex is required to be a leaf vertex in the solution Steiner tree. We present hardness results for this variant as well as a polynomial time approximation algorithm with performance ratio \(\rho+2\), where \(\rho\) is the best-known approximation ratio for the graph Steiner tree problem.