- INSTANCE: Graph , a weight function , and an integer .
- SOLUTION:
A subset
such that the subgraph
is connected and has no vertex with degree exceeding
*d*. - MEASURE:
The total weight of the subgraph, i.e.,
.

*Bad News:*Not in APX for any*d*[Kann, --].*Comment:*Transformation from LONGEST PATH. The problems have, indeed, the same non-approximability results.*Garey and Johnson:*GT26