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 mincut. 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 TwoFamilies 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 nearlinear in the size of G, improving on the previous O(n^{ω+1}). Furthermore, H recovers the closest mincut 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.
BibTeX  Entry
@InProceedings{he_et_al:LIPIcs.ESA.2021.52,
author = {He, Zhiyang and Li, Jason and Wahlstr\"{o}m, Magnus},
title = {{NearLinearTime, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {52:152:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14633},
URN = {urn:nbn:de:0030drops146331},
doi = {10.4230/LIPIcs.ESA.2021.52},
annote = {Keywords: graph theory, vertex sparsifier, representative family, matroid}
}
Keywords: 

graph theory, vertex sparsifier, representative family, matroid 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 