Pairwise Distance Preservers and Additive Spanners – University of Copenhagen

Pairwise Distance Preservers and Additive Spanners

Title: Pairwise Distance Preservers and Additive Spanners 

Abstract: Let G be a graph and let P be a set of node pairs.  The Pairwise Spanner question asks: what is the sparsest subgraph of G that approximately preserves all pairwise distances in P?  The special case P = V x V is simply called the Spanner question, and it is a very well known problem in graph theory.  When distances are to be preserved up to an additive error function, our understanding of what is possible in either of these problems seems to be quite poor. 

Meanwhile, the Pairwise Distance Preserver problem makes the restriction k=0; i.e. pairwise distances must be preserved exactly.  Our understanding of this problem is much better.  We will discuss some new upper bounds, and explain some plausible conjectures about what the true bounds might be. 

We will then discuss a new line of work that improves our understanding of spanners by reducing them to distance preservers.  In particular, we will overview a reduction from distance preserver upper bounds to spanner upper bounds, and a separate reduction from distance preserver lower bounds to spanner lower bounds.  Finally, we will mention some promising open problems whose resolution would imply further ties between these fields.

About the speaker: Greg Bodwin is a PhD student studying Theoretical Computer Science at Stanford University This summer he is visiting Mikkel Thorup's research group at the University of Copenhagen.

His main research interest is in combinatorics, graph theory, and their applications to algorithm design.