TY - GEN

T1 - Vertex sparsifiers

T2 - 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2010 and 14th International Workshop on Randomization and Computation, RANDOM 2010

AU - Englert, Matthias

AU - Gupta, Anupam

AU - Krauthgamer, Robert

AU - Räcke, Harald

AU - Talgam-Cohen, Inbal

AU - Talwar, Kunal

PY - 2010

Y1 - 2010

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 [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 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(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.

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 [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 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(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.

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

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

U2 - 10.1007/978-3-642-15369-3_12

DO - 10.1007/978-3-642-15369-3_12

M3 - Conference contribution

AN - SCOPUS:78149347698

SN - 3642153682

SN - 9783642153686

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 152

EP - 165

BT - Approximation, Randomization, and Combinatorial Optimization

Y2 - 1 September 2010 through 3 September 2010

ER -