网络流是伪多项式时间吗？

Question

我们知道正常的背包问题具有伪多项式时间,因为O(nW)的运行时间.我想知道网络流的运行时间是否是伪多项式时间,因为使用Ford-Fulkerson算法的网络流的运行时间是O(Cm)(m表示边数,C表示从起始点离开的边的容量之和) ？

Answer 1

是的,Ford-Fulkerson算法是伪多项式时间算法.它的运行时间是O(Cm),其中C是离开起始节点的容量之和.由于写出数字C需要O(log C)位,因此该运行时确实是伪多项式,但实际上不是多项式.

然而,存在用于最大流量的强多项式时间算法,例如在时间O(n ³)中运行的push-relabel算法.

希望这可以帮助!

@LearningToCode请记住,只有*问题*可以是P或NP,而不是*算法.* (3认同)
@LearningToCode 我给出的限制比他们列出的要严格一些。他们认为切割的最大尺寸不大于 EU 是正确的，但是您可以通过注意到仅删除 s 形成的切割具有最多 C 的容量（在我的符号中）来给出更严格的界限。至于这个问题是P还是NP-complete，因为我们有max-flow算法，其运行时间是强多项式（不是伪多项式），所以max-flow问题肯定是P的。它也有可能是NP-complete，但没有人知道，因为我们不知道 P = NP。（继续...） (2认同)