On the Size Overhead of Pairwise Spanners

Abstract

Given an undirected possibly weighted $n$-vertex graph $G=(V,E)$ and a set $\mathcal{P}\subseteq V^2$ of pairs, a subgraph $S=(V,E^{\prime })$ is called a $\mathcal{P}$-pairwise $\alpha$-spanner of $G$, if for every pair $(u,v)\in \mathcal{P}$ we have $d_S(u,v)\le \alpha \cdot d_G(u,v)$. The parameter $\alpha$ is called the stretch of the spanner, and its size overhead is define as $\frac{|E^{\prime }|}{|\mathcal{P}|}$. 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(\frac{1}{\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 $|\mathcal{P}|\approx n^{1+1/k}$, then a $\mathcal{P}$-pairwise $(1+\epsilon )$-spanner must have size at least $\beta \cdot |\mathcal{P}|$ with $\beta \approx {\left(\frac{1}{\epsilon }\right)}^{\log k}$ (a near matching upper bound was recently shown in \cite{ES23}). We also extend the connection between pairwise spanners and hopsets to the large stretch regime, by showing nearly matching upper and lower bounds for $\mathcal{P}$-pairwise $\alpha$-spanners. In particular, we show that if $|\mathcal{P}|\approx n^{1+1/k}$, then the size overhead is $\beta \approx \frac{k}{\alpha }$. A source-wise spanner is a special type of pairwise spanner, for which $\mathcal{P}=A\times V$ for some $A\subseteq V$. A prioritized spanner is given also a ranking of the vertices $V=(v_1,\dots ,v_n)$, and is required to provide improved stretch for pairs containing higher ranked vertices. By using a sequence of reductions, we improve on the state-of-the-art results for source-wise and prioritized spanners.

46 pages, 5 figures