- INSTANCE: Connected graph .
- SOLUTION:
A
*k*-spanner of*G*, i.e., a spanning subgraph*G'*of*G*such that, for any pair of vertices*u*and*v*, the length of the shortest path between*u*and*v*in*G'*is at most*k*times the distance between*u*and*v*in*G*. - MEASURE:
The number of edges in
*G'*.

*Good News:*Approximable within for*k=2*[333] and for [15].*Bad News:*Not approximable within , for some*c > 0*[332].*Comment:*In the edge-weighted case, the measure changes to the total weight of the spanner subgraph. In this case, the problem is still approximable within for*k=2*, but is hard to approximate within for any [332] () and [142] (). The variation in which the goal is to minimize the maximum degree in*G'*is approximable within where is the maximum degree in*G*[336]. See [142] for hardness of several other variants of the spanner problem.