Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs
share
In vertex-cut sparsification, given a graph G=(V,E) with a terminal set T⊆ V, we wish to construct a graph G'=(V',E') with T⊆ V', such that for every two sets of terminals A,B⊆ T, the size of a minimum (A,B)-vertex-cut in G' is the same as in G. In the most basic setting, G is unweighted and undirected, and we wish to bound the size of G' by a function of k=|T|. Kratsch and Wahlström [JACM 2020] proved that every graph G (possibly directed), admits a vertex-cut sparsifier G' with O(k^3) vertices, which can in fact be constructed in randomized polynomial time. We study (possibly directed) graphs G that are quasi-bipartite, i.e., every edge has at least one endpoint in T, and prove that they admit a vertex-cut sparsifier with O(k^2) edges and vertices, which can in fact be constructed in deterministic polynomial time. In fact, this bound naturally extends to all graphs with a small separator into bounded-size sets. Finally, we prove information-theoretically a nearly-matching lower bound, i.e., that Ω̃(k^2) edges are required to sparsify quasi-bipartite undirected graphs.
READ FULL TEXT