Given a capacitated graph *G = (V,E)* and a set of terminals *K
ße 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:

- 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. - 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}klog log k) - 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.

}, author = {Matthias Englert and Anupam Gupta and Robert Krauthgamer and Harald R{\"a}cke and Inbal Talgam-Cohen and Kunal Talwar}, booktitle = {APPROX 2010}, month = {September}, publisher = {Springer Verlag}, title = {Vertex Sparsifiers: New Results from Old Techniques}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=141076}, year = {2010}, }