Approximation of minimum weight spanners for sparse graphs

A t-spanner of a graph G is its spanning subgraph S such that the distance between every pair of vertices in S is at most t times their distance in G. The sparsestt-spanner problem asks to find, for a given graph G and an integer t, a t-spanner of G with the minimum number of edges. The problem is known to be NP-hard for all t≥2, and, even more, it is NP-hard to approximate it with ratio O(logn) for every t≥2. For t≥5, the problem remains NP-hard for planar graphs and the approximability status of the problem on planar graphs was open. We resolve this open issue by showing that the sparsestt-spanner problem admits the efficient polynomial time approximation scheme (EPTAS) for every t≥1. Our result holds for a much wider class of graphs, namely, the class of apex-minor-free graphs, which contains the classes of planar and bounded genus graphs. Moreover, it is possible to extend our results to weighted apex-minor free graphs, when the maximum edge weight is bounded by some constant.