Despite significant recent progress on approximating graph spanners (subgraphs which approximately preserve distances), there are still several large gaps in our understanding. We give new results for two of them: approximating basic k-spanner (particularly for small k), and the dependence on f when approximating f-fault tolerant spanners.

We first design an Õ(n^(1/3))-approximation for 4-spanner (both basic and directed). This was the last value of k for which only an O(√n)-approximation was known for basic k-spanner, and thus implies that for any k the approximation ratio is at most Õ(n^(1/3)). For basic k-spanner, we also show an integrality gap for the natural flow-based LP (the main tool in almost all nontrivial spanner approximations) which nearly matches the trivial approximation of n^{\frac{1}{\lfloor (k+1)/2\rfloor}}.

For f-fault tolerant spanners, we show that in the small-stretch setting (k ∈ {3,4}) it is possible to entirely remove the dependence on f from the approximation ratio, at the cost of moving to bicriteria guarantees. The previous best dependence on f was either almost-linear (in the undirected setting) or exponential (in the directed setting for stretch 4).