Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 4/14: Greg Bodwin on Linear-Sized Distance Preservers

Dan Michael Stubbs dstubbs at
Tue Apr 12 13:39:51 PDT 2016

Hi all,

We will have theory lunch this Thursday at the usual time (food at 12:15pm, talk at 12:30pm) and place (Gates 463A).   The speaker will be Greg Bodwin, who will tell us about distance preservers.

Be there!



Title: Linear-Sized Distance Preservers


Given a graph G = (V, E) and a set of node pairs P, a distance preserver is a sparse subgraph that exactly preserves all pairwise distances in P.  The most famous and well-applied result in distance preserver theory, commonly taught in undergraduate classes, is the "Shortest Path Tree Lemma:" if P has the structure P = {s} x V, then G, P has a distance preserver on O(n) (or equivalently O(|P|), because |P| = n) edges.

In many natural situations, however, P does not happen to have the convenient structure P = {s} x V.  Here, it is natural to wonder if the excellent O(n) or O(|P|) sparsity guarantees from Shortest Path Trees are still available despite the lack of structure on P.  That is the question we address in this work: can we ever say that all G, P has a preserver of size O(n) or O(|P|), without assuming any particular structure for the pair set P?

Surprisingly, the answer is yes!  We show:
(1) All G, P has a distance preserver on O(n) edges, so long as |P| = O(n^{1/3}).  This holds even if G is directed and/or weighted.
(2) All G, P has a distance preserver on O(|P|) edges, so long as |P| is "sufficiently large" (roughly |P| = n^2 / 2^{O(sqrt log n)}).

In this talk, we will overview these results, briefly discuss the computational problem of producing preservers within these sparsity bounds, and then discuss some interesting open questions that arise from this work.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list