为什么要找到最大切割 NP-hard？

Question

我最近发现在带有加权边的图中找到最大割是 NP 难的。然而，找到最小割并不是 NP 难的。如果我将所有边上的权重求逆，然后搜索最小割，那不会给我原始图上的最大割吗？如果不是，为什么？

Answer 1

我假设逆你的意思是将权重 w 更改为 -w 。

在这种情况下，调整后的图的最小割确实解决了原始图的最大割问题。

不幸的是，只有当所有权重都非负时，才能知道解决最小割问题的有效算法，这意味着只有所有权重都非正时，我们才能有效地解决最大割。

Answer 2

图的最大割不是具有逆权重的图的最小割。考虑下图：红线是最小切割，绿色是最大切割。

如果逆你的意思是“相反”，那么确实为一个找到最大值归结为为另一个找到最小切割。证明很简单。

设 G 为任意图，G' 为权重相反的图。让v_1,..., v_n是要移除的顶点序列以进行 G 的最大切割，以及w_1,..., w_n相关的权重。M = w_1 + ... + w_n = max(cuts). 显然v_1,..., v_n是 G' 的一个切入点。让v'_1,...,v'_mG' 中的任意切入和 G' 中w'_1,..., w'_n的权重。

然后v'_1,...,v'_m也是一个 G 的切入点-(w'_1+...+w'_q)。根据 M 的定义，我们有-(w'_1+...+w'_q) <= M等w'_1+...+w'_q >= -M。所以我们有 -M 是 G' 中的最小切割值并v_1,..., v_n实现这个值，它是G' 的最小切割值。

至于为什么这不是一个容易解决的问题，请参阅 Peter de Rivaz 的回答。