Vertex Sparsifiers: New Results from Old Techniques
Authors:
- Matthias EnglertMEMatthias Englert
- Anupam GuptaAGAnupam Gupta
- Robert KrauthgamerRKRobert Krauthgamer
- Harald RäckeHRHarald Räcke
- Inbal Talgam-CohenITInbal Talgam-Cohen
- Kunal TalwarKTKunal Talwar
Open Access
- 1 January 2014
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 43 (4) , 1239-1262
Abstract
Given a capacitated graph $G = (V,E)$ and a set of terminals $K \subseteq 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? Improving on results of Moitra [Proceedings of the 50th IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 2009, pp. 3--12] and Leighton and Moitra [Proceedings of the 42nd ACM Symposium on Theory of Computing, ACM, New York, 2010, pp. 47--56], we give efficient algorithms for constructing (a) a flow sparsifier $H$ that maintains congestion up to a factor of $O(\frac{\log k}{\log \log k})$, where $k = |K|$; (b) a convex combination of trees over the terminals $K$ that maintains congestion up to a factor of $O(\log k)$; (c) for a planar graph $G$, a convex combination of 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$. Moreover, this result extends to minor-closed families of graphs. Our bounds immediately imply improved approximation guarantees for several terminal-based cut and ordering problems.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability2010
- An improved approximation algorithm for requirement cutOperations Research Letters, 2010
- Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size2009
- Global connectivity potentials for random field models2009
- Expander flows, geometric embeddings and graph partitioningJournal of the ACM, 2009
- Graph cut based image segmentation with connectivity priors2008
- Extending Lipschitz functions via random metric partitionsInventiones Mathematicae, 2005
- A tight bound on approximating arbitrary metrics by tree metricsJournal of Computer and System Sciences, 2004
- Cuts, Trees and ℓ1-Embeddings of Graphs*Combinatorica, 2004
- Divide-and-conquer approximation algorithms via spreading metricsJournal of the ACM, 2000