## Vertex Sparsification: An Introduction, Connections and Applications

Ankur Moitra
Massachusetts Institute of Technology; Institute for Advanced Study
November 8, 2011 - 10:30am

The notion of exactly (or approximately) representing certain combinatorial properties of a graph \$G\$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, I will introduce the notion of vertex sparsification. Here we are given a graph \$G = (V, E)\$ and a set of terminals \$K \subset V\$ and our goal is to find one single graph \$H = (K, E_H)\$ on just the terminal set so that \$H\$ approximately preserves the minimum cut between every bi-partition of the terminals.

Standard results in combinatorial optimization are concerned with minimum cuts between "small" subsets of the terminals - .e.g. Mader's theorem implies that if we are interested in the minimum cuts between each pair of terminals, there is a graph \$H\$ on just the set of terminals that exactly represents these \${K \choose 2}\$ values. Yet in our setting, we are interested in minimum cuts between "large" subsets of terminals as well - e.g. the minimum bisection of the terminals. One might wonder whether good vertex sparsifiers exist. There are two orthogonal challenges that we must overcome - first, the minimum cuts that we are interested contain the answers to "hard" optimization problems and second, we must approximately preserve exponentially many values using only \${K \choose 2}\$ degrees of freedom.

Nevertheless, I will prove that good vertex sparsifiers do exist and in fact the approximation factor is independent of the size of the original graph (and is sub-logarithmic in the number of terminals). Moreover, the approximation factor can be improved to a constant for naturally arising graphs - namely those that exclude any fixed minor. I will give a number of results in this context which will give me an excuse to build connections to metric embeddings, fourier analysis and linear programming hierarchies. Lastly, I will also give a number of applications (all based on the pattern of using a good vertex sparsifier as a proxy for the original graph) including a master theorem for flow-cut gaps.

Parts of this talk will be based on joint work with Tom Leighton, and Moses Charikar and Shi Li.

Hi-Res716.28 MB
Lo-Res387.6 MB