  Given a graph $G = (V,E)$ and a subset $T \subseteq V$ of terminals, a
\emph{Steiner tree} of $G$ is a tree that spans $T$. In the vertex-weighted
Steiner tree (VST) problem, each vertex is assigned a non-negative weight, and
the goal is to compute a minimum weight Steiner tree of $G$.
  We study a natural generalization of the VST problem motivated by multi-level
graph construction, the \emph{vertex-weighted grade-of-service Steiner tree
problem} (V-GSST), which can be stated as follows: given a graph $G$ and
terminals $T$, where each terminal $v \in T$ requires a facility of a minimum
grade of service $R(v)\in \{1,2,\ldots\ell\}$, compute a Steiner tree $G'$ by
installing facilities on a subset of vertices, such that any two vertices
requiring a certain grade of service are connected by a path in $G'$ with the
minimum grade of service or better. Facilities of higher grade are more costly
than facilities of lower grade. Multi-level variants such as this one can be
useful in network design problems where vertices may require facilities of
varying priority.
  While similar problems have been studied in the edge-weighted case, they have
not been studied as well in the more general vertex-weighted case. We first
describe a simple heuristic for the V-GSST problem whose approximation ratio
depends on $\ell$, the number of grades of service. We then generalize the
greedy algorithm of [Klein \& Ravi, 1995] to show that the V-GSST problem
admits a $(2 \ln |T|)$-approximation, where $T$ is the set of terminals
requiring some facility. This result is surprising, as it shows that the
(seemingly harder) multi-grade problem can be approximated as well as the VST
problem, and that the approximation ratio does not depend on the number of
grades of service.
