Optimal Vertex-Cut Sparsification of Quasi-Bipartite Graphs

Itai Boneh, Robert Krauthgamer

In vertex-cut sparsification, given a graph $G=(V,E)$ with a terminal set $T\subseteq V$, we wish to construct a graph $G^{\prime }=(V^{\prime },E^{\prime })$ with $T\subseteq V^{\prime }$, such that for every two se…