Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs

Zhiyang He, Jason Li, Magnus Wahlström

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$,…