MINIMUM EDGE K-SPANNER

• INSTANCE: Connected graph $G=\left(V,E\right)$.
• 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 $O(\log\vert E\vert/\vert V\vert)$ for k=2 [333] and $O(\vert V\vert^{1/k})$ for $k\ge 3$ [15].
• Bad News: Not approximable within $c \log \vert V\vert/k$, 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 $O(\log\vert E\vert/\vert V\vert)$ for k=2, but is hard to approximate within $2^{\log^{1-\varepsilon } \vert V\vert}$ for any $\varepsilon >0$ [332] ($k\ge 5$) and [142] ($k\ge 3$). The variation in which the goal is to minimize the maximum degree in G' is approximable within $O(\sqrt{\log\vert V\vert}\Delta^{1/4})$ where $\Delta$ is the maximum degree in G [336]. See [142] for hardness of several other variants of the spanner problem.