Small Stretch Pairwise Spanners and Approximate $D$-Preservers
Telikepalli Kavitha, Nithin M. Varma · SIAM Journal on Discrete Mathematics · 2015
Let $G = (V,E)$ be an undirected unweighted graph on $n$ vertices. A subgraph $H$ of $G$ is called a purely additive spanner of $G$ with stretch $\beta$ if for each $(u,v) \in V \times V$, the $u$-$v$ distance in $H$ is at most $\delta_G(u,v) + \beta$. We currently know sparse purely additive spanners with $\beta = O(1)$ only for $\beta = 2,4,6$. When $\beta = 2$, the size of the spanner is $O(n^{3/2})$; when $\beta = 4$, the size of the spanner is $O(n^{1.4}\log^{0.2}n)$; and when $\beta = 6$, the size of the spanner is $O(n^{4/3})$. The following is a natural relaxation of the above problem: we care for only certain distances, these are captured by the set $\mathcal{P} \subseteq V \times V$, and the problem is to construct a sparse subgraph $H$ (also called a $\mathcal{P}$-spanner), where for every $(u,v) \in \mathcal{P}$, the $u$-$v$ distance in $H$ is at most $\delta_G(u,v) + \beta$. In this paper we show algorithms to construct the following for $\beta = 2$: a $\mathcal{P}$-spanner of size $\tilde{O}(n|\mathcal{P}|^{1/3})$ for any $\mathcal{P}\subseteq V\times V$ and a $\mathcal{P}$-spanner of size $\tilde{O}(n|\mathcal{P}|^{1/4})$ when $\mathcal{P} = S \times V$, where $S \subseteq V$. Our $\mathcal{P}$-spanner with additive stretch 2 leads to a simple deterministic construction of a purely additive spanner with stretch 4 and size $O(n^{1.4}\log^{0.2}n)$. We also consider a variant of the $\mathcal{P}$-spanner problem where the set $\mathcal{P}$ is implicitly given via a distance threshold $D$. That is, $\mathcal{P} = \{(u,v): \delta_G(u,v) \ge D\}$. We refer to such a $\mathcal{P}$-spanner as an approximate $D$-preserver. A $D$-preserver is a subgraph where distances $\ge D$ are exactly preserved and $D$-preservers of size $O(n^2/D)$ are known. For a given $D \in \mathbb{Z}^+$ and any integer $k \ge 1$, we construct an $\tilde{O}(n^{3/2}/D^{k/(2k+2)})$-sized subgraph where distances $\ge D$ are approximated with an additive stretch of $4k$. In particular, when $k = \lfloor\log D\rfloor$, this subgraph has size $\tilde{O}(n\cdot\sqrt{n/D})$.