我知道检查加权有向图的给定边是否属于负循环的问题是 NP 完全的（找到包含所有负循环的最小子图）并且 Bellman-Ford 允许在 O( |V|*|E|) 时间。但是如果我想找到所有属于负循环的顶点呢？我想知道它是否可以比 Floyd-Warshall 的 O(|V|^3) 更快。
问问题
1563 次
1 回答
1
我不认为 Floyd-Warshall 能找到这些顶点。使用您所指的帖子中采用的类似方法，可以证明找到位于负循环上的所有顶点的集合也是 NP 完全的。
相关帖子表明，可以使用该算法找到位于负循环上的所有边的集合来解决哈密顿循环问题，这意味着前一个问题是 NP 完全的。如果我们可以将找到位于负循环上的所有边的问题简化为找到位于负循环上的所有顶点的集合的问题，我们已经证明了后一个问题的 NP 完全性。
对于加权有向图中的每条边 (u,w)，引入一个新的辅助顶点 v，并将 (u, w) 拆分为两条边 (u, v) 和 (v, w)。(u, w) 的权重可以分配给 (u, v) 或 (v, w)。现在应用魔术多项式时间算法来查找位于负循环上的所有顶点，并获取由辅助顶点组成的子集。由于每个辅助顶点都与一条边相关联，我们已经解决了寻找包含所有负循环的最小子图的问题，因此我们也可以在多项式时间内解决哈密顿循环问题，这意味着 P = NP。假设 P != NP，找到位于负循环上的所有顶点是 NP 完全的。
于 2013-05-24T08:58:31.007 回答