• Calendar

July 2, Tuesday
12:00 – 13:00

A key challenge in designing graph algorithms is to compress a graph $G$ so as to preserve some of its basic properties, such as distances and cuts. Both spanners [Peleg and Schaffer, 1989] and cut sparsifiers [Benczur and Karger, 1996] fall into this category, as they reduce the number of edges in $G$ without changing any distance or cut by more than a bounded factor.

I will discuss another flavor of this challenge, which asks instead to reduce the number of vertices. Specifically, given a graph $G$ and $k$ terminal vertices, we wish to construct a small graph that is a minor of $G$, and in which all the terminal distances equal those in $G$ (exactly). Can we bound the size of $G'$ by some function of $k$? I will also talk about a similar question regarding terminal cuts, called mimicking networks by [Hagerup, Katajainen, Nishimura, and Ragde, 1998].

Joint works with Inbal Rika and with Tamar Zondiner.