Cygan, Marek ;
Grandoni, Fabrizio ;
Kavitha, Telikepalli
On Pairwise Spanners
Abstract
Given an undirected nnode unweighted graph G = (V, E), a spanner with stretch function f(.) is a subgraph H \subseteq G such that, if two nodes are at distance d in G, then they are at distance at most f(d) in H. 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 uv distance only for pairs (u,v) in a given set P \subseteq V x V. Such Pspanners were studied before [Coppersmith,Elkin'05] only in the special case that f(.) 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 P) and of the best known spanners (with the same f(.)).
In more detail, for arbitrary P, we show that there exists a Pspanner of size O(n(Plog n)^{1/4}) with f(d) = d + 4 log n. Alternatively, for any epsislon > 0, there exists a Pspanner of size O(nP^{1/4} sqrt{(log n) / epsilon}) with f(d) = (1 + epsilon)d + 4. We also consider the relevant special case that there is a critical set of nodes S \subseteq V, and we wish to approximate either the distances within nodes in S or from nodes in S to any other node. We show that there exists an (S x S)spanner of size O(n sqrt{S}) with f(d) = d + 2, and an (S x V)spanner of size O(n sqrt{S log n}) with f(d) = d + 2 log n. All the mentioned pairwise spanners can be constructed in polynomial time.
BibTeX  Entry
@InProceedings{cygan_et_al:LIPIcs:2013:3935,
author = {Marek Cygan and Fabrizio Grandoni and Telikepalli Kavitha},
title = {{On Pairwise Spanners}},
booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
pages = {209220},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897507},
ISSN = {18688969},
year = {2013},
volume = {20},
editor = {Natacha Portier and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/3935},
URN = {urn:nbn:de:0030drops39353},
doi = {10.4230/LIPIcs.STACS.2013.209},
annote = {Keywords: Undirected graphs, shortest paths, additive spanners, distance preservers}
}
26.02.2013
Keywords: 

Undirected graphs, shortest paths, additive spanners, distance preservers 
Seminar: 

30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Issue date: 

2013 
Date of publication: 

26.02.2013 