This meeting will be a talk on sparse distance preservers of graphs given by Greg Bodwin.
Title: Distance Preservers
Abstract: One of the most fundamental and useful facts in computer science is the existence of BFS trees: given a graph G = (V, E) and a source node s, there is a tree that preserves all pairwise distances in P = {s} x V. But what if we want to preserve distances between an arbitrary set of node pairs, which doesn’t happen to have the structure P = {s} x V? How big does a distance-preserving subgraph then need to be?
In this talk, we will show that the answer is “surprisingly small,” and that in many nontrivial situations you only need O(n) edges in the subgraph. We’ll describe a new yet simple way to think of shortest paths in graphs, escaping the influence of BFS Trees, and we’ll discuss a few open problems on the frontier of research on distance preservers.
First meeting of the semester was a problem session! We had donuts as well as a few very interesting problems about discrete structures, probability, and set theory.
continue reading ❯