TY - JOUR

T1 - Vertex sparsifiers

T2 - New results from old techniques

AU - Englert, Matthias

AU - Gupta, Anupam

AU - Krauthgamer, Robert

AU - R̈acke, Harald

AU - Talgam-Cohen, Inbal

AU - Talwar, Kunal

PY - 2014

Y1 - 2014

N2 - 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 [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 ( 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.[[amp]]copy;2014 SIAM. Published by SIAM under the terms.

AB - 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 [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 ( 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.[[amp]]copy;2014 SIAM. Published by SIAM under the terms.

KW - 0-extensions

KW - Approximation algorithms

KW - Flow sparsifier

KW - Graph minors

KW - Metric decomposition

KW - Multicommodity flow

KW - Planar graphs

KW - Vertex sparsifier

UR - http://www.scopus.com/inward/record.url?scp=84906816570&partnerID=8YFLogxK

U2 - 10.1137/130908440

DO - 10.1137/130908440

M3 - Article

AN - SCOPUS:84906816570

SN - 0097-5397

VL - 43

SP - 1239

EP - 1262

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 4

ER -