Please note: This seminar will take place in DC 2306 and online.
Gary Hoppenworth, PhD candidate
Electrical Engineering & Computer Science, University of Michigan
Given a graph G, a distance preserver is a sparse subgraph H of G that exactly preserves shortest path distances between a small set of demand pairs P \subseteq V(G) \times V(G) in G. The study of distance preservers is primarily focused on the following question: How many edges are needed to construct a distance preserver of an n-vertex graph G with respect to a set P of p=|P| demand pairs? Distance preservers were first introduced by Coppersmith and Elkin in [SODA'06] and have connections to extremal graph theory and incidence geometry.
In the first part of this talk, we will review what is known about distance preservers. Some highlights include: 1) We will introduce a property of shortest paths known as ‘consistency’, and we will use consistency to bound the size of distance preservers by the number of edges in a graph avoiding a certain forbidden subgraph. 2) We will discuss a conjecture on distance preservers that generalizes the classical Szemeredi-Trotter Theorem of discrete geometry to finite metrics.
In the second part of this talk, we will present two new results related to distance preservers. First, we will present an extremal reduction from distance preservers in directed graphs to distance preservers in undirected graphs. This reduction has the property that any improvement in undirected distance preserver upper bounds in the regime of p \leq n would imply improved directed distance preserver upper bounds as well. Along the way, we prove the following algorithmic result: All-Pairs Shortest Paths (APSP) in directed acyclic graphs can be reduced to APSP in undirected graphs in O(m) time. Second, we will present new upper bounds for distance preservers in unweighted directed graphs. Upper bounds for distance preservers in unweighted undirected graphs were previously studied by Bodwin and Vassilevska Williams in [SODA’20].
The second part of this talk is based on joint work with Yinzhan Xu and Zixuan Xu.
To attend this seminar in person, please go to C 2306. You can also attend virtually using Zoom.