标题： 一种简单快速的从Gomory-Hu树到多对数最大流的约简 显示英文标题

标题： A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows

摘要： 给定一个无向图$G=(V,E,w)$，Gomory-Hu树$T$（Gomory和Hu，1961）是在$V$上的一个树，它精确地保留了$G$的所有点对最小割。我们提出了一种将Gomory-Hu树简化为polylog最大流计算的高效归约方法。在无权图上，我们的归约简化为总实例大小为$\tilde{O}(m)$的图上的最大流计算，算法仅需要$\tilde{O}(m)$的额外时间。我们的归约是第一个在polylog因子范围内紧致的归约。该归约也无缝扩展到加权图，然而实例大小和运行时间增加到$\tilde{O}(n^2)$。最后，我们展示了如何将我们的归约扩展到将无权超图的Gomory-Hu树归约为超图中的最大流。同样，我们的归约是第一个在polylog因子范围内紧致的归约。 显示英文摘要

摘要： Given an undirected graph $G=(V,E,w)$, a Gomory-Hu tree $T$ (Gomory and Hu, 1961) is a tree on $V$ that preserves all-pairs mincuts of $G$ exactly. We present a simple, efficient reduction from Gomory-Hu trees to polylog maxflow computations. On unweighted graphs, our reduction reduces to maxflow computations on graphs of total instance size $\tilde{O}(m)$ and the algorithm requires only $\tilde{O}(m)$ additional time. Our reduction is the first that is tight up to polylog factors. The reduction also seamlessly extends to weighted graphs, however, instance sizes and runtime increase to $\tilde{O}(n^2)$. Finally, we show how to extend our reduction to reduce Gomory-Hu trees for unweighted hypergraphs to maxflow in hypergraphs. Again, our reduction is the first that is tight up to polylog factors.