algorithm - 无向图中的最小割

Question

我想引用 Wikipedia

In mathematics, the minimum k-cut, is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to k connected components.

如果边的集合是最小的，则称它是最小割。

对于 k = 2，这意味着找到一组边，删除这些边会将图形断开成 2 个连接组件。

但是，维基百科的同一篇文章说:

For a fixed k, the problem is polynomial time solvable in O(|V|^(k^2))

我的问题是这是否意味着最小 2-cut 是属于复杂度等级 P 的问题？

Answer 1

最小割问题可以在多项式时间内解决，因此是的，它确实属于复杂度类 P。与此特定问题相关的另一篇文章是 Max-flow min-cut theorem .