- INSTANCE:
Graph
,
weight
and length
for each ,
positive integer
*B*. - SOLUTION:
A spanning subgraph
for
*G*such that the sum of the weights of the edges in*E'*does not exceed*B*. - MEASURE:
The diameter of the spanning subgraph.

*Bad News:*Not approximable within 2 for any [405].*Comment:*Not approximable within 3/2 for planar graphs. Not approximable within 5/4 if*l(e)=1*for every edge*e*[405]. For results on minimum Steiner trees of bounded diameter, see MINIMUM STEINER TREE.*Garey and Johnson:*Similar to ND4