text: Given an undirected @math -node unweighted graph @math , a spanner with stretch function @math is a subgraph @math such that, if two nodes are at distance @math in @math , then they are at distance at most @math in @math . Spanners are very well studied in the literature. The typical goal is to construct the sparsest possible spanner for a given stretch function. In this paper we study pairwise spanners, where we require to approximate the @math - @math distance only for pairs @math in a given set @math . Such @math -spanners were studied before [Coppersmith,Elkin'05] only in the special case that @math is the identity function, i.e. distances between relevant pairs must be preserved exactly (a.k.a. pairwise preservers). Here we present pairwise spanners which are at the same time sparser than the best known preservers (on the same @math ) and of the best known spanners (with the same @math ). In more detail, for arbitrary @math , we show that there exists a @math -spanner of size @math with @math . Alternatively, for any @math , there exists a @math -spanner of size @math with @math . We also consider the relevant special case that there is a critical set of nodes @math , and we wish to approximate either the distances within nodes in @math or from nodes in @math to any other node. We show that there exists an @math -spanner of size @math with @math , and an @math -spanner of size @math with @math . All the mentioned pairwise spanners can be constructed in polynomial time.
  @cite_9: We introduce and study the notions of pair-wise and source-wise preservers.Given an undirected N-vertex graph G = (V, E) and a subset P of pairs of vertices, let G' = (V, H), H ⊆ E, be called a pair-wise preserver of G with respect to P if for every pair u, w ∈ P, dist G' (u, w) = dist G (u, w). For a set S ⊆ V of sources, a pair-wise preserver of G with respect to the set of all pairs P = (S 2) of sources is called a source-wise preserver of G with respect to S.We prove that for every undirected possibly weighted N-vertex graph G and every subset P of P = O(N1 2) pairs of vertices of G, there exists a linear-size pair-wise preserver of G with respect to P. Consequently, for every subset S ⊆ V of S = O(N1 4) sources, there exists a linear-size source-wise preserver of G with respect to S. On the negative side we show that neither of the two exponents (1 2 and 1 4) can be improved even when the attention is restricted to unweighted graphs.Our lower bounds involve constructions of dense convexly independent sets of vectors with small Euclidean norms. We believe that the link between the areas of Discrete Geometry and spanners that we establish is of independent interest, and might be useful in the study of other problems in the area of low-distortion embeddings.
summary: Compared to the preservers in @cite_9 , we achieve sparser pairwise spanners with additive stretch @math for @math , and a sparser subsetwise spanners for @math . Interestingly, our sourcewise spanners are always sparser than the pairwise preservers from @cite_9 .