Theory of Computing
-------------------
Title     : Lowest-Degree $k$-Spanner: Approximation and Hardness
Authors   : Eden Chlamtac and Michael Dinitz
Volume    : 12
Number    : 15
Pages     : 1-29
URL       : https://theoryofcomputing.org/articles/v012a015

Abstract
--------

A $k$-spanner is a subgraph in which distances are approximately
preserved, up to some given stretch factor $k$. We focus on the
following problem: Given a graph and a value $k$, can we find a
$k$-spanner that minimizes the maximum degree? While reasonably strong
bounds are known for some spanner problems, they almost all involve
minimizing the total number of edges. Switching the objective to the
degree introduces significant new challenges, and currently the only
known approximation bound is an $\tilde O(\Delta^{3-2\sqrt{2}})$-
approximation for the special case when $k=2$ [Chlamtač, Dinitz, 
Krauthgamer FOCS 2012] (where $\Delta$ is the maximum degree
in the input graph). In this paper we give the first non-trivial
algorithm and polynomial-factor hardness of approximation for the case
of arbitrary constant $k$. Specifically, we give an LP-based 
$\tilde O(\Delta^{(1-1/k)^2})$-approximation and prove that it is hard 
to approximate the optimum to within $\Delta^{\Omega(1/k)}$ when the
graph is undirected, and to within $\Delta^{\Omega(1)}$ when it is
directed.

An extended abstract of this paper appeared in the Proceedings of
the 17th International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX 2014).