On the Size Overhead of Pairwise Spanners
Ofer Neiman, Idan Ben Shabat · SSRN Electronic Journal · 2025
Given an undirected weighted $n$-vertex graph $G=(V,E)$ and a set $\mathcal{P}\subseteq V^2$, a subgraph $S=(V,E')$ is called a ${\cal P}$-pairwise $\alpha$-spanner of $G$, if for every $(u,v)\in\mathcal{P}$ we have $d_S(u,v)\leq\alpha\cdot d_G(u,v)$ ($\alpha$ is called the stretch). A surprising connection was recently discussed between the additive stretch of $(1+\epsilon,\beta)$-spanners, to the hopbound of $(1+\epsilon,\beta)$-hopsets. A long sequence of works showed that if the spanner/hopset has size $\approx n^{1+1/k}$ for some parameter $k\ge 1$, then $\beta\approx\left(\frac1\epsilon\right)^{\log k}$. In this paper we establish a new connection to the size overhead of pairwise spanners. In particular, we show that if $|{\cal P}|\approx n^{1+1/k}$, then a ${\cal P}$-pairwise $(1+\epsilon)$-spanner must have size at least $\beta\cdot |{\cal P}|$ with $\beta\approx\left(\frac1\epsilon\right)^{\log k}$ (a near matching upper bound was recently shown).We also show that the size overhead and the hopbound of hopsets admit nearly matching upper and lower bounds, even when the stretch is some $\alpha\gg1+\epsilon$.