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}_+ \rightarrow \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 $\delta>0$ and constant integer $k\geq 2$, every graph on $n$ vertices has a sublinear additive spanner with stretch function $f(d)=d+O(d^{ 1-1/k})$ and $O\big(n^{ 1+\frac{ 1+\delta}{ 2^{ k+1}-1}}\big)$ 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\geq 3$, this improves upon the previous spanner construction with stretch function $f(d) = d + O(d^{ 1-1/k})$ and $O\bigg(n^{ 1+\frac{ (3/4)^{ k-2}}{ 7 - 2\cdot (3/4)^{ k-2}}}\bigg)$ edges. Most importantly, the size of our spanners almost matches the lower bound of $\Omega\big(n^{ 1+\frac{ 1}{ 2^{ k+1}-1}}\big)$, 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+\varepsilon})$ 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.
Categories: cs.DS