Vertex Sparsifiers and Oblivious Reductions

Sep 29, 2010

The notion of exactly representing or approximately preserving certain combinatorial properties of a graph $G$ on a simpler graph is ubiquitous in combinatorial optimization. In this talk, we introduce the notion of vertex cut and flow 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 congestion of _every_ multicommodity flow in which the demands have endpoints in $K $. In practice this implies that any optimization problem over cuts or flows can instead be solved on $H$ as a proxy for running directly on $G$, and still returns a solution of approximately the same value. We prove good vertex sparsifiers exist, and we also give efficient algorithms for computing good vertex sparsifiers. As a consequence we are able to obtain approximation algorithms with guarantees independent of the size of the graph for a number of graph partitioning, graph layout and multicommodity flow problems for which such guarantees were previously unknown. In fact, these results follow from a generic reduction that only requires that an optimization problem can be characterized by the value of all cuts and flows.

This talk will be loosely based on three papers, Moitra "Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size" (FOCS 2009), Tom Leighton, Moitra "Extensions and Limits to Vertex Sparsification" (STOC 2010), and Moses Charikar, Tom Leighton, Shi Li, Moitra "Vertex Sparsification and Abstract Rounding Algorithms" (FOCS 2010).

This talk will be loosely based on three papers, Moitra "Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size" (FOCS 2009), Tom Leighton, Moitra "Extensions and Limits to Vertex Sparsification" (STOC 2010), and Moses Charikar, Tom Leighton, Shi Li, Moitra "Vertex Sparsification and Abstract Rounding Algorithms" (FOCS 2010).