Lightweight Near-Additive Spanners

arXiv:2410.23826v1 Announce Type: new
Abstract: An $(alpha,beta)$-spanner of a weighted graph $G=(V,E)$, is a subgraph $H$ such that for every $u,vin V$, $d_G(u,v) le d_H(u,v)lealphacdot d_G(u,v)+beta$. 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 $alpha=1+varepsilon$ for arbitrarily small $varepsilon>0$. We show the first construction of {em light} spanners in this setting. Specifically, for any integer parameter $kge 1$, we obtain an $(1+varepsilon,O(k/varepsilon)^kcdot 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(kn^{1+3/k})$.