Next: MAXIMUM K-COLORABLE INDUCED SUBGRAPH Up: Subgraphs and Supergraphs Previous: MAXIMUM EDGE SUBGRAPH Index

### MINIMUM EDGE 2-SPANNER

- 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 [316], for k=2.

- Bad News: Not approximable within , for some c > 0 [315].

- Comment: The good news holds also in the edge weighted case [315]. The edge weighted case for is hard to approximate within for any unless [315].

  The variation in which the goal is to minimize the maximum degree in G' is approximable within where is the maximum degree in G [318].