Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.

## Description

The notion of vertex sparsification (in particular cut-sparsification) is introduced in (M, 2009), where it was shown that for any graph \$G = (V, E)\$ and a subset of \$k\$ terminals \$K subset V\$, there is a polynomial time algorithm to construct a graph \$H = (K, E_H)\$ emph{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\$, yielding approximation guarantees independent of the size of the graph. In this work, we consider how well cuts in the sparsifier \$H\$ can approximate the minimum cuts in \$G\$, and whether algorithms that use such reductions need to incur a multiplicative penalty in the approximation guarantee depending on the quality of the sparsifier.

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 \$Omega(log^{1/4} k)\$ -- this is polynomially-related to the known upper bound of \$O(log k/log log k)\$. This is an exponential improvement on the \$Omega(log log k)\$ bound given in (LM, 2010) 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. Roughly, we show that any rounding algorithm which also works for the \$0\$-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 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 integr