Abstract
Given a capacitated graph G = (V,E) and a set of terminals K ⊆ 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 [FOCS 2009] and Leighton and Moitra [STOC 2010], we give efficient algorithms for constructing: (a) a flow-sparsifier H that maintains congestion up to a factor of \({\smash{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(logk). (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.
A full version appears at http://arxiv.org/abs/1006.4586
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Andersen, R., Feige, U.: Interchanging distance and capacity in probabilistic mappings. CoRR, abs/0907.3631 (2009)
Archer, A., Fakcharoenphol, J., Harrelson, C., Krauthgamer, R., Talwar, K., Tardos, É.: Approximate classification via earthmover metrics. In: Proc. 15th SODA, pp. 1079–1087 (2004)
Calinescu, G., Karloff, H.J., Rabani, Y.: Approximation algorithms for the 0-extension problem. SIAM J. Comput. 34(2), 358–372 (2004)
Fakcharoenphol, J., Harrelson, C., Rao, S., Talwar, K.: An improved approximation algorithm for the 0-extension problem. In: Proc. 14th SODA, pp. 257–265 (2003)
Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. System Sci. 69(3), 485–497 (2004)
Fakcharoenphol, J., Talwar, K.: Improved decompositions of graphs with forbidden minors. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) 6th APPROX. LNCS, vol. 2764, pp. 36–46. Springer, Heidelberg (2003)
Gupta, A., Nagarajan, V., Ravi, R.: Improved approximation algorithms for requirement cut. Operations Research Letters 38(4), 322–325 (2010)
Gupta, A., Newman, I., Rabinovich, Y., Sinclair, A.: Cuts, trees and ℓ1-embeddings of graphs. Combinatorica 24(2), 233–269 (2004)
Gupta, A.: Steiner points in tree metrics don’t (really) help. In: Proc. 12th SODA, pp. 220–227 (2001)
Klein, P., Plotkin, S.A., Rao, S.B.: Excluded minors, network decomposition, and multicommodity flow. In: Proc. 25th STOC, pp. 682–690 (1993)
Leighton, T., Moitra, A.: Extensions and limits to vertex sparsification. In: Proc. 42th STOC, pp. 47–56 (2010)
Lee, J.R., Naor, A.: Extending Lipschitz functions via random metric partitions. Invent. Math. 160(1), 59–95 (2005)
Lee, J.R., Sidiropoulos, A.: On the geometry of graphs with a forbidden minor. In: Proc. 41st STOC, pp. 245–254 (2009)
Moitra, A.: Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In: Proc. 50th FOCS, pp. 3–12 (2009)
Nowozin, S., Lampert, C.H.: Global connectivity potentials for random field models. In: Proc. 22nd CVPR, pp. 818–825 (2009)
Räcke, H.: Optimal hierarchical decompositions for congestion minimization in net works. In: Proc. 40th STOC, pp. 255–264 (2008)
Vicente, S., Kolmogorov, V., Rother, C.: Graph cut based image segmentation with connectivity priors. In: Proc. 21st CVPR (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Englert, M., Gupta, A., Krauthgamer, R., Räcke, H., Talgam-Cohen, I., Talwar, K. (2010). Vertex Sparsifiers: New Results from Old Techniques. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. RANDOM APPROX 2010 2010. Lecture Notes in Computer Science, vol 6302. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15369-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-15369-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15368-6
Online ISBN: 978-3-642-15369-3
eBook Packages: Computer ScienceComputer Science (R0)