Low-distortion Graph Spanners
Seth Pettie, Max Planck Institut für Informatik
Friday, March 3rd, 2006, 3:30 pm
Wean Hall 7220

Abstract

A spanner H of an undirected, unweighted graph G is a subgraph such that the distance between two points w.r.t. H is not too far from their distance in G, where "not too far" is captured by a distortion function f. Specifically, H is an f-spanner if dist_H(u,v) is at most f(dist_G(u,v)). Nearly all work on spanners and related structures considered only multiplicative distortion, and, in general, provided an undesirable tradeoff between the size of H and the coefficient of distortion.

The "holy grail" question in this area is whether there exist arbitrarily sparse spanners whose distortion is additive and constant. It was known that any graph has an additive 2-spanner with O(n^{3/2}) edges. In this talk I'll present a completely new method for constructing spanners based on an economics-inspired view of the problem. The main result is an additive 6-spanner with O(n^{4/3}) edges. In addition, the technique leads to a spectrum of arbitrarily sparse spanners whose distortion is additive and sublinear in the distance being approximated.