论文标题
在有向无环图中的接近线性时间，最佳顶点切割稀疏器
Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
论文作者
论文摘要
令$ g $为图形，$ s，t \ subseteq v（g）$ be（可能是重叠）终端集，$ | s | = | t | = k $。我们有兴趣计算一个以$ g $削减终端削减的顶点刺激器，即在最小可能数量的顶点上$ g $，其中$ s \ s \ cup t \ subseteq v（h）$，因此每个$ a \ a \ subseteq s $ and $ b \ subseteq s $ and $ b \ subseteq t $ a s $ a $ cut a a $ a $ c的$（ $ h $。我们假设我们的图形未加权，并且终端可能是最小切割的一部分。在先前的工作中，Kratsch和Wahlström（Focs 2012/JACM 2020）使用与Matroid理论的连接表明，即使是在随机的多项式时间内，即使是针对任意digraphs $ g $，也可以在随机的多项式时间内计算出$ o（k^3）$ o（k^3）$ pertices的顶点sparsifier $ h $。但是，从那时起，就没有显示$ O（k^3）$的改进。 在本文中，我们从著名的Bollobás的两个餐厅定理中汲取了灵感，并将总订单的使用介绍到Kratsch和Wahlström的方法中。这种新的视角使我们能够为$ g $是一个dag构建$θ（k^2）$顶点的稀疏器$ h $。我们还展示了如何以$ g $的大小计算$ h $ nime接近线性，从而改善了上一个$ o（n^{ω+1}）$。此外，$ h $为每个分区$（a，b）$恢复了最接近的$ g $，这是以前不知道的。最后，我们表明，对于DAG和无向边缘切割，都需要大小$ω（k^2）$的稀疏器。
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öm (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á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^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^{ω+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^2)$ is required, both for DAGs and for undirected edge cuts.
