Small Stretch Pairwise Spanners and D Spanners

An additive spanner of an undirected graph is a subgraph in which the shortest distance between any pair of vertices is larger than the corresponding distance in the original graph by at most an additive term. This additive term is called the stretch of that spanner. Additive spanners are very well studied. They have applications in compact routing schemes, near shortest path algorithms, approximate distance oracles, etc. A natural relaxation of the above problem is where the approximation requirement applies only to a subset of pairs of vertices. Subgraphs satisfying this relaxed requirement are called pairwise spanners. A $D$-spanner is a pairwise spanner for which the set of pairs of vertices to be approximated are all those that are at a distance at least $D$ in the original graph. It is NP-hard to compute the sparsest additive pairwise spanner of a graph for any given stretch. The typical goal is to design algorithms which for specific values of stretch, construct pairwise spanners that are as sparse as possible.

In this talk we will present a brief survey of the work done in the area of pairwise spanners, the important algorithmic techniques used in constructing them and high level ideas of some of our algorithms for additive pairwise spanners.