Tight Bound on Vertex Cut Sparsifiers in Directed Acyclic Graphs.
Zhiyang He, Jason Li · arXiv (Cornell University) · 2020
For an unweighted graph on $k$ terminals, Kratsch and Wahlstrom constructed a vertex sparsifier with $O(k^3)$ vertices via the theory of representative families on matroids. Since their breakthrough result in 2012, no improvement upon the $O(k^3)$ bound has been found. In this paper, we interpret Kratsch and Wahlstrom's result through the lens of Bollobas's Two-Families Theorem from extremal combinatorics. This new perspective allows us to close the gap for directed acyclic graphs and obtain a tight bound of $\Theta(k^2)$. Central to our approach is the concept of skew-symmetry from extremal combinatorics, and we derive a similar theory for the representation of skew-symmetric families that may have future applications.