Volume 12 (2016) Article 15 pp. 1-29
APPROX-RANDOM 2014 Special Issue
Lowest-Degree $k$-Spanner: Approximation and Hardness
by
Revised: July 20, 2016
Published: September 24, 2016
[PDF (418K)]       [PS.GZ (0K)]
[Source ZIP]
Keywords: approximation algorithms, hardness of approximation, graph spanners
ACM Classification: G.2.2, F.2.2, G.1.6
AMS Classification: 68W25, 68Q17, 05C85

Abstract: [Plain Text Version]

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$ [Chlamtáč, 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).