New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
复制标题
无向图中所有对最大流的新算法和下界
DOI：
10.1137/1.9781611975994.4
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Ohad Trabelsi
中科院分区：
文献类型：
--
作者：
Amir Abboud;Robert Krauthgamer;Ohad Trabelsi
我们研究了全对最大流问题的时间复杂度：给定一个有$n$个节点和$m$条边的图，计算所有节点对之间的最大流值。如果最大流（具有给定源-汇对的版本）可以在时间T（m）$内求解，则时间复杂度为O（n^2）\cdot T（m）$。但我们能做得更好吗？
对于有向图，最近的细粒度复杂性结果表明，这个时间界限基本上是最优的。相比之下，对于具有边容量的无向图，Gomory和Hu（1961）的开创性算法运行时间要快得多$O（n）\cdot T（m）$。在最大流可以在近似线性时间$m^{1+o（1）}$内求解的合理假设下，这个半个世纪前的算法产生了$nm^{1+o（1）}$界。多年来，已经设计了其他几种算法，包括单位容量边缘的$\tilde{O}（mn）$时间（无条件），但它们都没有突破$O（mn）$障碍。同时，对于无向图，也没有给出超线性下界。
我们设计的第一个硬度减少无向图中的所有对最大流，给$\textit{node-capacities}$设置一个基本上最优的下界。对于边容量，我们证明类似下界的努力失败了，但是我们发现了一个令人惊讶的新算法，它打破了具有单位容量边的图的$O（mn）$障碍！假设$T（m）=m^{1+o（1）}$，我们的算法在时间$m^{3/2 +o（1）}$上运行，并输出一个割等价树（类似于Gomory-Hu算法）。时间复杂度为O（n^{5/3-\vareps}）$。最后，我们通过证明一个$\textit{non-reducing}$结果来解释下界的缺乏。这个结果是基于一个新的准线性时间$\tilde{O}（m）$ $\textit{非确定性}$算法构造一个割等价树，可能是独立的兴趣。
We investigate the time-complexity of the All-Pairs Max-Flow problem: Given a graph with $n$ nodes and $m$ edges, compute for all pairs of nodes the maximum-flow value between them. If Max-Flow (the version with a given source-sink pair $s,t$) can be solved in time $T(m)$, then an $O(n^2) \cdot T(m)$ is a trivial upper bound. But can we do better?
For directed graphs, recent results in fine-grained complexity suggest that this time bound is essentially optimal. In contrast, for undirected graphs with edge capacities, a seminal algorithm of Gomory and Hu (1961) runs in much faster time $O(n)\cdot T(m)$. Under the plausible assumption that Max-Flow can be solved in near-linear time $m^{1+o(1)}$, this half-century old algorithm yields an $nm^{1+o(1)}$ bound. Several other algorithms have been designed through the years, including $\tilde{O}(mn)$ time for unit-capacity edges (unconditionally), but none of them break the $O(mn)$ barrier. Meanwhile, no super-linear lower bound was shown for undirected graphs.
We design the first hardness reductions for All-Pairs Max-Flow in undirected graphs, giving an essentially optimal lower bound for the $\textit{node-capacities}$ setting. For edge capacities, our efforts to prove similar lower bounds have failed, but we have discovered a surprising new algorithm that breaks the $O(mn)$ barrier for graphs with unit-capacity edges! Assuming $T(m)=m^{1+o(1)}$, our algorithm runs in time $m^{3/2 +o(1)}$ and outputs a cut-equivalent tree (similarly to the Gomory-Hu algorithm). Even with current Max-Flow algorithms we improve state-of-the-art as long as $m=O(n^{5/3-\varepsilon})$. Finally, we explain the lack of lower bounds by proving a $\textit{non-reducibility}$ result. This result is based on a new quasi-linear time $\tilde{O}(m)$ $\textit{non-deterministic}$ algorithm for constructing a cut-equivalent tree and may be of independent interest.
DOI：
10.1007/s10817-013-9289-2
发表时间：
2014
期刊：
Journal of Automated Reasoning
影响因子：
--
作者：
E. Alkassar;S. Böhme;K. Mehlhorn;C. Rizkallah
通讯作者：
C. Rizkallah
DOI：
10.1145/3357713.3384247
发表时间：
2019-10
期刊：
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Yang P. Liu;Aaron Sidford
通讯作者：
Yang P. Liu;Aaron Sidford