algorithm - 有向强连通图中所有顶点对的最小切割

Question

我有一个图 G，它是一个有向且强连通的图，我被要求找到所有顶点对的最小割，这意味着图中的每一对 S 和 T。这应该在 O(m ² × n ² ) 时间内完成。

我想出的最好的方法是将所有顶点视为 S，并且对于每个 S，将所有其他顶点视为 T，并且对每个顶点运行 Ford-Fulkerson 算法，然后找到最小割。但如果我没记错的话，这个算法的复杂度是 O(m ² × n ² × C)。

我怎样才能在 O(m ² × n ² ) 时间内完成这项任务？甚至可能吗？

Answer 1

符号：：
m边
n数：节点数
c_max：最大单边容量
C：最大流量值。

可以使用Dinic 的算法来解决手头的任务。它运行在O(m * n^2). 最小割计算的蛮力方法O(n^2)然后产生总和O(m * n^2 * n^2)，这是 的期望结果m = O(n^2)。对于m = o(n^2)我找不到明确结果的稀疏图；然而，对于m = O(n) 本文给出的结果为O(n^2 + n^4 * log n) = O(m^2 * n^2 * log n).

有几种算法可以计算复杂度低于 的有向图中的最小切割（或等效地，最大流量）O( m * n^2 )。Wilf HS，算法和复杂性，第 1 版。在第 65 页有一个调查。最容易理解的算法可能是 Dinic ( O(m * n^2))。

虽然乍一看，福特-富克森算法的时间复杂度很高O( m * C )，但它也有一些严重的缺点：

• 时间复杂度仅对整数边缘容量有效。事实上，由于边缘容量不合理，该算法甚至不能保证完全终止，也不能收敛到最大流量（请参阅这篇论文以获取可证明的最小反例；在维基百科文章中也引用了这篇论文）。

• 时间复杂度取决于最大流量的值。

流量值的意义

最大流量值C不一定是节点和边数的函数。即使是（取决于图拓扑），以下观察成立：任何图中的最大可能流值是边数乘以最大边容量，m * c_max等于O(m)。

这将整数边容量的 Ford-Fulkerson 复杂度变为O(m^2)，除非单个边的最大容量是图中节点或边数的函数，这是一个非标准假设。

对于其他算法没有影响，因为它的执行取决于图拓扑和相对于彼此的边缘容量，而不是绝对边缘容量（因此，也不是最大流量值的函数）。