Spring 2015 Seminar Series

DATE: 4/9/15
LOCATION: E51-395
TIME: 4:15pm
Reception immediately following

SPEAKER:
Robert Krauthgamer

TITLE
Vertex Sparsification of Cuts, Flows, and Distances

ABSTRACT
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 small 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 G' that contains the terminals, such that all cuts/flows/distances between the terminals are equal in G and in G'. Can we bound the size of G' by a function of k? And what if G' only needs to approximate G (say within 1+epsilon)?

 

I plan to survey recent progress in this emerging area.