Almost-Optimal Sublinear Additive Spanners

Abstract

Given an undirected unweighted graph $G=(V,E)$ on $n$ vertices and $m$ edges, a subgraph $H\subseteq G$ is a spanner of $G$ with stretch function $f:{\mathbb{R}}_{+}\to {\mathbb{R}}_{+}$, if for every pair $s,t$ of vertices in $V$, ${\text{dist}}_H(s,t)\le f({\text{dist}}_G(s,t))$. When $f(d)=d+o(d)$, $H$ is called a sublinear additive spanner; when $f(d)=d+o(n)$, $H$ is called an \emph{additive spanner}, and $f(d)-d$ is usually called the \emph{additive stretch} of $H$. As our primary result, we show that for any constant $\hat{I}´>0$ and constant integer $k\ge 2$, every graph on $n$ vertices has a sublinear additive spanner with stretch function $f(d)=d+O(d^{1-1/k})$ and $O\left(n^{1+\frac{1+\hat{I}´}{2^{k+1}-1}}\right)$ edges. When $k=2$, this improves upon the previous spanner construction with stretch function $f(d)=d+O(d^{1/2})$ and $\tilde{O}(n^{1+3/17})$ edges; for any constant integer $k\ge 3$, this improves upon the previous spanner construction with stretch function $f(d)=d+O(d^{1-1/k})$ and $O\left(n^{1+\frac{(3/4{)}^{k-2}}{7-2\cdot (3/4{)}^{k-2}}}\right)$ edges. Most importantly, the size of our spanners almost matches the lower bound of $\hat{I}\text{c◯}\left(n^{1+\frac{1}{2^{k+1}-1}}\right)$, which holds for all compression schemes achieving the same stretch function. As our second result, we show a new construction of additive spanners with stretch $O(n^{0.403})$ and $\tilde{O}(n)$ edges, which slightly improves upon the previous stretch bound of $O(n^{3/7+\epsilon })$ achieved by linear-size spanners. An additional advantage of our spanner is that it admits a subquadratic construction runtime of $\tilde{O}(m+n^{13/7})$, while the previous construction requires all-pairs shortest paths computation which takes $O(\min \{mn,n^{2.373}\})$ time.