For an unweighted graph on kterminals , Kratsch and Wahlstr\"om 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 Wahlstr\"om's result through the lens of Bollob\'as'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). Furthermore, H recovers the closest min-cut in G for every partition (A,B), which was not previously known. Finally, we show that a sparsifier of size \Omega(k^2) is required, both for DAGs and for undirected edge cuts} .
Let G be a graph and S, T \subseteq V(G) be (possibly overlapping) sets of terminals, |S|=|T|=k. We are interested in computing a vertex sparsifier for terminal cuts in G, i.e., a graph H on a smallest possible number of vertices, where S \cup T \subseteq V(H) and such that for every A \subseteq S and B \subseteq T the size of a minimum (A,B)-vertex cut is the same in G as in H. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work , Kratsch and Wahlstr\"om (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier H with O(k^3) vertices can be computed in randomized polynomial time, even for arbitrary digraphs G. However, since then, no improvements on the size O(k^3) have been shown . In this paper, we draw inspiration from the renowned Bollob\'as's Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlstr\"om's methods . This new perspective allows us to construct a sparsifier H of \Theta(k^2) vertices for the case that G is a DAG. We also show how to compute H in time near-linear in the size of G, improving on the previous O(n^{\omega+1). Furthermore, H recovers the closest min-cut in G for every partition (A,B), which was not previously known. Finally, we show that a sparsifier of size \Omega(k^2) is required, both for DAGs and for undirected edge cuts} .
R
For an unweighted graph on kterminals
Let G be a graph and S, T \subseteq V(G) be (possibly overlapping) sets of terminals, |S|=|T|=k. We are interested in computing a vertex sparsifier for terminal cuts in G, i.e., a graph H on a smallest possible number of vertices, where S \cup T \subseteq V(H) and such that for every A \subseteq S and B \subseteq T the size of a minimum (A,B)-vertex cut is the same in G as in H. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work
R
constructed
(FOCS 2012/JACM 2020) used connections to matroid theory to show that
A
H
R
via the theory of representative families on matroids. Since their breakthrough result in 2012, no improvement upon the
can be computed in randomized polynomial time, even for arbitrary digraphs G. However, since then, no improvements on the size
R
bound has been found
have been shown
R
interpret Kratsch and Wahlstr\"om's result through the lens of
draw inspiration from the renowned
R
from extremal combinatorics
in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlstr\"om's methods
R
close the gap for directed acyclic graphs and obtain a tight bound
construct a sparsifier H
R
. 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
vertices for the case that G is a DAG. We also show how to compute H in time near-linear in the size of G, improving on the previous O(n^{\omega+1