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


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

Questions and Answers

You need to be logged in to be able to post here.