Lightweight Near-Additive Spanners

Abstract

An $(\hat{I}\pm ,{\hat{I}}^2)$-spanner of a weighted graph $G=(V,E)$, is a subgraph $H$ such that for every $u,v\in V$, $d_G(u,v)\le d_H(u,v)\le \hat{I}\pm \cdot d_G(u,v)+{\hat{I}}^2$. The main parameters of interest for spanners are their size (number of edges) and their lightness (the ratio between the total weight of $H$ to the weight of a minimum spanning tree). In this paper we focus on near-additive spanners, where $\hat{I}\pm =1+\epsilon$ for arbitrarily small $\epsilon >0$. We show the first construction of {\em light} spanners in this setting. Specifically, for any integer parameter $k\ge 1$, we obtain an $(1+\epsilon ,O(k/\epsilon {)}^k\cdot W(\cdot ,\cdot ))$-spanner with lightness $\tilde{O}(n^{1/k})$ (where $W(\cdot ,\cdot )$ indicates for every pair $u,v\in V$ the heaviest edge in some shortest path between $u,v$). In addition, we can also bound the number of edges in our spanner by $O(k{n}^{1+3/k})$.

Appeared in WG24