Approximate Gomory-Hu Tree Is Faster Than n-1 Max-Flows
Approximate Gomory-Hu Tree Is Faster Than n-1 Max-Flows
复制标题
近似 Gomory-Hu 树比 n-1 最大流更快
DOI：
10.1145/3406325.3451112
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Panigrahi, Debmalya
中科院分区：
文献类型：
--
作者：
Li, Jason;Panigrahi, Debmalya
Gomory-Hu树或切树（Gomory and Hu, 1961）是一种经典的数据结构，用于无向图中所有垂直对的报告-最小切（以及对偶性，s - tmaxflows的值）。Gomory和Hu表明，它可以用n−1精确的maxflow计算来计算。令人惊讶的是，50多年后，这仍然是Gomory-Hu树的最佳算法，即使是近似的最小切。在本文中，我们打破了这个长期存在的障碍，并给出了一个使用log(n) maxflow计算计算(1+ n) -近似Gomory-Hu树的算法。具体来说，我们将获得下面描述的运行时边界。我们获得了一种随机（蒙特卡罗）算法，用于无向加权图，该算法运行在Õ（m+ n2 /2）时间内，并返回(1+ n)-近似gomori - hu树算法whp。在此之前，已知的最佳运行时间为Õ（n5/2），这是通过在图的切割稀疏器上运行Gomory和Hu的原始算法得到的。接下来，我们获得了一种针对无向、无加权图的随机化（蒙特卡罗）算法，该算法运行时间为m4/3+o(1)，并返回(1+ k)-近似Gomory-Hu树算法whp。这改进了我们对稀疏图的第一个结果，即m= 0 （n9/8）。以前，对于一个精确的Gomory-Hu树，已知的未加权图的最佳运行时间为Õ（mn） （Bhalgatet al., STOC 2007）；如果允许近似值，没有更好的结果。由于我们的Gomory-Hu树算法，我们还在同一时间范围内解决了(1+ n)-近似的所有对最小切和单源最小切问题。（这些问题更简单，因为目标是只返回这些- mincut值，而不是mincut值。）这改进了Abboud等人（FOCS 2020）在Õ（n2）时间内解决这些问题的最新算法。
The Gomory-Hu tree or cut tree (Gomory and Hu, 1961) is a classic data structure for reportings−tmincuts (and by duality, the values ofs−tmaxflows) for all pairs of verticessandtin an undirected graph. Gomory and Hu showed that it can be computed usingn−1 exact maxflow computations. Surprisingly, this remains the best algorithm for Gomory-Hu trees more than 50 years later, even for approximate mincuts. In this paper, we break this longstanding barrier and give an algorithm for computing a (1+є)-approximate Gomory-Hu tree using log(n) maxflow computations. Specifically, we obtain the runtime bounds we describe below.We obtain a randomized (Monte Carlo) algorithm for undirected, weighted graphs that runs in Õ(m+n3/2) time and returns a (1+є)-approximate Gomory-Hu tree algorithm whp. Previously, the best running time known was Õ(n5/2), which is obtained by running Gomory and Hu’s original algorithm on a cut sparsifier of the graph.Next, we obtain a randomized (Monte Carlo) algorithm for undirected, unweighted graphs that runs inm4/3+o(1)time and returns a (1+є)-approximate Gomory-Hu tree algorithm whp. This improves on our first result for sparse graphs, namelym=o(n9/8). Previously, the best running time known for unweighted graphs was Õ(mn) for an exact Gomory-Hu tree (Bhalgatet al., STOC 2007); no better result was known if approximations are allowed.As a consequence of our Gomory-Hu tree algorithms, we also solve the (1+є)-approximate all pairs mincut and single source mincut problems in the same time bounds. (These problems are simpler in that the goal is to only return thes−tmincut values, and not the mincuts.) This improves on the recent algorithm for these problems in Õ(n2) time due to Abboud et al. (FOCS 2020).