寻找包含所有负循环的最小子图

Question

4

我遇到了以下问题：给定一个加权有向图G，我想构建包含所有负（简单）环的最小子图。

我知道如何使用Bellman-Ford找到负环，并且我知道有向图中简单环的数量是指数级别的。

一种朴素的方法是简单地迭代所有简单环并选择负环，但我感觉可能存在多项式时间算法。通过谷歌搜索得到的大多数文章都是关于找到（而不是所有）负环的。

我希望在stackoverflow上找到一些专家，他们可以提供关于多项式时间解决方案的提示，或者提供证明它不能在多项式时间内解决的提示。

非常感谢！

- robertdg

这可能更适合在数学或计算机理论交流中讨论。 - wich

@ninjagecko：[作业]标签现在正在逐步淘汰，请参见元。 - Mechanical snail

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- robertdg · Accepted Answer

对于任何对此感兴趣或陷入类似问题的人：它是NP完全问题。感谢wich指向cstheory中的线程。

要了解为什么它是NP完全问题，首先观察问题可以表述如下：给定一张带有N个顶点和边E的加权有向图G，找出E是否位于（简单）负环上。如果是，则E应该在子图H中。如果不是，则不应该在H中。

现在，让边E =（u，v）且权重为w。我们想知道是否存在一条从v到u的路径，其总权重为W，使得W + w <0。如果我们可以在多项式时间内做到这一点，我们也可以在多项式时间内解决Hamiltonian Cycle问题：

将边E的权重分配为N-1.00001。将图中所有其他边的权重分配为-1。现在，图上唯一的负循环是包含所有顶点的循环（该循环的权重为-0.00001），因此是Hamiltonian Cycle。

非常感谢您的思考！