New Pairwise Spanners

Let G=(V,E) be an undirected unweighted graph on n vertices. A subgraph H of G is called an (all-pairs) purely additive spanner with stretch β if for every (u,v)∈V×V, d i s t _H (u,v)≤d i s t _G (u,v) + β. The problem of computing sparse spanners with small stretch β is well-studied. Here we consider the following variant: we are given \(\mathcal {P} \subseteq V \times V\) and we seek a sparse subgraph H where d i s t _H (u,v)≤d i s t _G (u,v) + β for each \((u,v) \in \mathcal {P}\). That is, distances for pairs outside \(\mathcal {P}\) need not be well-approximated in H. Such a subgraph is called a pairwise spanner with additive stretch β and our goal is to construct such subgraphs that are sparser than all-pairs spanners with the same stretch. We show sparse pairwise spanners with additive stretch 4 and with additive stretch 6. We also consider the following special cases: \(\mathcal {P} = S \times V\) and \(\mathcal {P} = S \times T\), where S⊆V and T⊆V, and show sparser pairwise spanners for these cases.