Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs

Abstract

Let G be a graph and S, T ⊆ 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 ∪ T ⊆ V(H) and such that for every A ⊆ S and B ⊆ 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öm (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier H with O(k³) vertices can be computed in randomized polynomial time, even for arbitrary digraphs G. However, since then, no improvements on the size O(k³) have been shown.
In this paper, we draw inspiration from the renowned Bollobás’s Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlström’s methods. This new perspective allows us to construct a sparsifier H of Θ(k²) 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^{ω+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 Ω(k²) is required, both for DAGs and for undirected edge cuts.