Abstract
Given a graph $G$ with a subset $|T|=k$ of its vertices called terminals, a \emph{quality-$q$ cut sparsifier} is a graph $G'$ that contains $T$, such that, for any partition $(T_1,T_2)$ of $T$ into non-empty subsets, the value of a min-cut in $G$ separating $T_1$ from $T_2$ is within factor $q$ from the value of a min-cut in $G$ separating $T_1$ from $T_2$. The construction of cut sparsifiers with good (small) quality and (small) size has been a central problem in graph compression for years.
Planar graphs and quasi-bipartite graphs are two important special families studied in this research direction. The main results in this paper are new cut sparsifier constructions for them in the high-quality regime (where $q=1$ or $1+\eps$ for small $\eps>0$).
We first show that every planar graph admits a planar quality-$(1+\eps)$ cut sparsifier of size $\tilde O(k/\poly(\eps))$, which is in sharp contrast with the lower bound of $2^{\Omega(k)}$ for the quality-$1$ case.
We then show that every quasi-bipartite graph admits a quality-$1$ cut sparsifier of size $k^{O(k^2)}$. This is the second to improve over the doubly-exponential bound for general graphs (previously, only planar graphs have been shown to have single-exponential size quality-$1$ cut sparsifiers).
Lastly, we show that contraction, a common approach for constructing cut sparsifiers adopted in most previous works, does not always give optimal bounds for cut sparsifiers. We demonstrate this by showing that the optimal size bound for quality-$(1+\eps)$ contraction-based cut sparsifiers for quasi-bipartite graphs lies in the range $[k^{\Omega(1/\eps)},k^{O(1/\eps^2)}]$, while in previous work a $\poly(k/\eps)$ upper bound was achieved via a non-contraction approach.
This is a joint work with Zihan Tan.