- INSTANCE:
Graph
,
positive integer .
- SOLUTION:
An augmenting set
*E'*for*G*, i.e., a set*E'*of unordered pairs of vertices from*V*, such that has diameter*D*, i.e., the maximum distance of any pair of vertices is at most*D*. - MEASURE:
Cardinality of the augmenting set, i.e., .

*Bad News:*As hard to approximate as MINIMUM SET COVER [355].*Comment:*Variation in which the size of the augmenting set is bounded by*D*and the problem is to minimize the diameter is approximable within [355].