Vertex Sparsifiers: New Results from Old Techniques

Matthias Englert, Anupam Gupta, Robert Krauthgamer, Harald Räcke, Inbal Talgam-Cohen, and Kunal Talwar

September 2010

Given a capacitated graph $G = (V,E)$ and a set of terminals $K \sse V$, how should we produce a graph $H$ only on the terminals $K$ so that every (multicommodity) flow between the terminals in $G$ could be supported in $H$ with low congestion, and vice versa? (Such a graph $H$ is called a flow-sparsifier for $G$.) What if we want $H$ to be a "simple'' graph? What if we allow $H$ to be a convex combination of simple graphs? Such problems were studied by Moitra [FOCS 2009] and Leighton and Moitra [STOC 2010].

In this paper, we improve on their results and show the following:

(a) We show how to efficiently construct flow-sparsifiers $H$ which maintain congestion up to a factor of $\log k / \log\log k$, where $k = |K|$. This improves the previous result of Leighton and Moitra [STOC 2010] by an $O(\log k)$ factor.

(b) We construct a distribution of trees over the terminals $K$ that maintains congestion up to a factor of $O(\log k)$. The best results previously were $O(\log n)$ and $O(\frac{\log^3 k}{\log\log k})$.

(c) Given terminals in a planar graph, we construct distributions over planar graphs that maintains congestion up to a constant factor. This requires us to give a new algorithm for the 0-extension problem, the first one in which the preimages of each terminal are connected in $G$; this result extends to minor-closed families of graphs.

These results immediately improve the approximation algorithms for several terminal-based cut and ordering problems. (We also give direct algorithms for the ordering problems with better approximation guarantees.) Apart from these positive results, we also give some lower bounds for restricted classes of flow-sparsifiers.

PDF file |

In APPROX 2010

Publisher Springer Verlag

Type | Inproceedings |

> Publications > Vertex Sparsifiers: New Results from Old Techniques