Vertex Sparsifiers and Abstract Rounding Algorithms

The notion of vertex sparsification (in particular cut-sparsification) is introduced in, where it was shown that for any graph G = (V, E) and any subset of k terminals K ⊂ V, there is a polynomial time algorithm to construct a graph H = (K, E H ) on just the terminal set so that simultaneously for all cuts (A, K-A), the value of the minimum cut in G separating A from K-A is approximately the same as the value of the corresponding cut in H. Then approximation algorithms can be run directly on H as a proxy for running on G. We give the first super-constant lower bounds for how well a cut-sparsifier H can simultaneously approximate all minimum cuts in G. We prove a lower bound of Ω(log 1/4 k) this is polynomially-related to the known upper bound of O(log k/log log k). Independently, a similar lower bound is given in. This is an exponential improvement on the Ω(log log k) bound given in which in fact was for a stronger vertex sparsification guarantee, and did not apply to cut sparsifiers. Despite this negative result, we show that for many natural optimization problems, we do not need to incur a multiplicative penalty for our reduction. Roughly, we show that any rounding algorithm which also works for the O-extension relaxation can be used to construct good vertex-sparsifiers for which the optimization problem is easy. Using this, we obtain optimal O(log k)-competitive Steiner oblivious routing schemes, which generalize the results in. We also demonstrate that for a wide range of graph packing problems (which includes maximum concurrent flow, maximum multiflow and multicast routing, among others, as a special case), the integrality gap of the linear program is always at most O(log k) times the integrality gap restricted to trees. Lastly, we use our ideas to give an efficient construction for vertex-sparsifiers that match the current best existential results - this was previously open. Our algorithm makes novel use of Earth-mover constraints.

Authors

• Moses Charikar
• Frank Thomson Leighton
• Shi Li 0001
• Ankur Moitra

Keywords

• Approximation methods
• Approximation algorithms
• Routing
• Polynomials
• Measurement
• Optimization
• Hamming weight
• Rounding Algorithm
• Lower Bound
• Optimization Problem
• Upper Bound
• Estimation Algorithm
• Linear Programming
• Maximum Flow
• Packing Problem
• Minimum Cut
• Distance Function
• Feasible Solution
• Structural Inequalities
• Flow Problem
• Hamming Distance
• Automorphism
• Graph Partitioning
• Spanning Tree
• Integral Solution
• Flow Algorithm
• Boolean Function
• Competitive Ratio
• Partitioning Problem
• Terminal Pair
• Concurrent Problems
• Set Of Demands
• Strong Duality
• Integration Rule
• Linear Programming Relaxation
• Cut Set
• vertex sparsifier