2026-07-25T15:15:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14633 2024-03-06T10:54:30Z ddc:004 open_access

Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs He, Zhiyang Li, Jason Wahlström, Magnus graph theory vertex sparsifier representative family matroid 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zhiyang He and Jason Li and Magnus Wahlström 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.52 urn:nbn:de:0030-drops-146331 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.52 eng https://creativecommons.org/licenses/by/4.0/legalcode