论文标题
切割等效的树非常适合最小的查询
Cut-Equivalent Trees are Optimal for Min-Cut Queries
论文作者
论文摘要
最低点的查询是基本的：预处理一个无方向的边缘加权图，以快速报告最小重量的切割，该切口将一对查询对节点$ s，t $分开。该问题已知的最佳数据结构只是建造了一棵剪裁等效的树，该树由Gomory和Hu发现，他们还展示了如何使用$ n-1 $最低$ ST $ cut计算来构建它。使用最低限度的最低算法$ st $ -cut（Lee and Sidford，focs，2014）Arxiv：1312.6713，可以在时间$ \ tilde {o}（Mn^{3/2}）$中构造树木，这也是数据结构的预处理时间。 （在整个过程中，我们专注于多项式结合的边缘重量，并指出更快的算法以小/单位边缘的重量而闻名。） 我们的主要结果显示了以下等效性：当且仅当存在近乎线性预处理时间的最低点查询时，可以在接近线性的时间内构建切割等效的树，即使查询将查询限制在固定源中时，也可以使用几乎线性的预处理时间和pologrogarithmic（amortized）查询时间。也就是说，等效的树是最佳查询的最佳解决方案。即使对于每个次要封闭的图形家族，例如有界树木的图形，这种等效性也具有，其中两个十年的旧数据结构（Arikati等，J。〜Algorithms 1998）意味着切割等效树的第一个接近线性的时间构造。 此外，与以前所有用于构建剪裁等效树的技术不同，我们的依赖近似算法具有鲁棒性。特别是，使用$（1+ε）$ - 最低$ s $ st $ -cut（Kelner等，Soda，2014）的几乎线性时间算法，我们可以在时间$ n^{2+o（2+o（1+n^notion）中，我们可以构造$（1+ε）$ - 近似流量等于这导致了第一个$（1+ε）$ - 全对最大流量的近似值，该近似是$ n^{2+o（1）} $，并且几乎非常优势匹配输出大小。
Min-Cut queries are fundamental: Preprocess an undirected edge-weighted graph, to quickly report a minimum-weight cut that separates a query pair of nodes $s,t$. The best data structure known for this problem simply builds a cut-equivalent tree, discovered 60 years ago by Gomory and Hu, who also showed how to construct it using $n-1$ minimum $st$-cut computations. Using state-of-the-art algorithms for minimum $st$-cut (Lee and Sidford, FOCS 2014) arXiv:1312.6713, one can construct the tree in time $\tilde{O}(mn^{3/2})$, which is also the preprocessing time of the data structure. (Throughout, we focus on polynomially-bounded edge weights, noting that faster algorithms are known for small/unit edge weights.) Our main result shows the following equivalence: Cut-equivalent trees can be constructed in near-linear time if and only if there is a data structure for Min-Cut queries with near-linear preprocessing time and polylogarithmic (amortized) query time, and even if the queries are restricted to a fixed source. That is, equivalent trees are an essentially optimal solution for Min-Cut queries. This equivalence holds even for every minor-closed family of graphs, such as bounded-treewidth graphs, for which a two-decade old data structure (Arikati et al., J.~Algorithms 1998) implies the first near-linear time construction of cut-equivalent trees. Moreover, unlike all previous techniques for constructing cut-equivalent trees, ours is robust to relying on approximation algorithms. In particular, using the almost-linear time algorithm for $(1+ε)$-approximate minimum $st$-cut (Kelner et al., SODA 2014), we can construct a $(1+ε)$-approximate flow-equivalent tree (which is a slightly weaker notion) in time $n^{2+o(1)}$. This leads to the first $(1+ε)$-approximation for All-Pairs Max-Flow that runs in time $n^{2+o(1)}$, and matches the output size almost-optimally.
