Computer Science/Discrete Mathematics Seminar II

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.