Vertex Sparsifiers and Abstract Rounding Algorithms

The notion of vertex sparsification is introduced in \cite{M}, where it was shown that for any graph $G=(V,E)$ and a subset of $k$ terminals $K \subset V$,thereisapolynomialtimealgorithmtoconstructagraph$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$. 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 $\mathrm{\Omega }({\log }^{1\mathrm{/}4}k)$ – this is polynomially-related to the known upper bound of $O(\log k\mathrm{/}\log \log k)$. This is an exponential improvement on the $\mathrm{\Omega }(\log \log k)$ bound given in \cite{LM} 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 problems, we do not need to incur a multiplicative penalty for our reduction. We obtain optimal $O(\log k)$-competitive Steiner oblivious routing schemes, which generalize the results in \cite{R}. 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. This result helps to explain the ubiquity of the $O(\log k)$ guarantees for such problems. 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.