In this paper, the authors derive a polynomial time approximation scheme (PTAS) for the weight-constrained minimum cost Steiner tree problem (WCSTP) for a special class of graphs, knows as series-parallel (S-P) graphs. An S-P graph is a subgraph of a 2-tree that describes an extremely important class of fault tolerant networks.

The contributions of this paper are its proof that the WCSTP is NP-hard, even for this special case of S-P graphs, and its definition of an algorithm that computes an approximate solution in strongly polynomial time. The proof of NP-hardness of the WCSTP is based on the transformation of the partition problem to the problem under consideration in an S-P graph. In section 3, the authors present a pseudo-polynomial time algorithm for computing a minimum weight Steiner tree with cost bounded by a constant. In section 4, standard scaling and rounding techniques are used to turn the previously proposed algorithm into a strongly polynomial time approximation scheme for the WCSTP. The paper is well written, and the results and algorithms are clearly presented. In my opinion, however, it would have been beneficial if the authors included a section on the possible (and important) applications of WCSTP for the special class of S-P graphs.