Expander Flows, Graph Spectra and Graph Separators
| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | Expander Flows, Graph Spectra and Graph Separators |
| Speaker: | Umesh Vazirani |
| Affiliation: | University of California, Berkeley |
| Date: | Monday, December 3 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
A graph separator is a set of edges whose deletion partitions the graph into two (or more) pieces. Finding small graph separators is a fundamental combinatorial problem with numerous applications. Interest in it also derives from its theoretical connections to spectral methods, linear/semi-definite programming, high dimensional geometry and measure concentration.
In this talk I will speak about approximation algorithms for this problem that are (within poly log factors) as fast as max-flow computations. The analysis of these algorithms is based on a cut-matching game, a new embedding of the graph in R^n called the walk-embedding, and the notion of {\em expander flows}, introduced in [ARV], which constitute an interesting ``certificate'' of a graph's expansion.
Based on joint work with Khandekar and Rao, and Orrechia, Schulman and Vishnoi.