我遇到了以下问题：给定一个加权有向图 G，我想构建 G 的最小子图，其中包含 G 的所有负（简单）循环。
我确实知道如何使用 Bellman-Ford 找到负循环，而且我知道有向图中的简单循环数是指数级的。
解决这个问题的一种天真的方法是简单地迭代所有简单的循环并选择那些是负数的，但我觉得可能存在多项式时间算法。我通过 Google 找到的大多数文章都是关于寻找（而不是全部）负循环的。
我希望在这里找到一些关于 stackoverflow 的专家，他们可能会为多项式时间解决方案提供一些提示，或者提示证明它不能在多项式时间内解决。
提前谢谢了！
干杯，罗伯特
对于任何对类似问题感兴趣或陷入困境的人：它是 NP 完全的。感谢 wich 将我指向 cstheory 中的线程。
要了解它为什么是 NP 完全的，首先观察问题可以表述如下：给定一个具有 N 个顶点和 G 上的边 E 的加权有向图 G，找出 E 是否位于（简单）负循环上。如果是，E 应该在子图 H 中。如果不是，它不应该在 H 中。
现在，让边 E 为 E = (u, v)，权重为 w。我们想知道是否存在一条从 v 到 u 且总权重为 W 且 W + w < 0 的路径。如果我们可以在多项式时间内做到这一点，我们也可以在多项式时间内解决哈密顿循环问题：
为边 E 分配 N - 1.00001 的权重。为图中的所有其他边分配 -1 的权重。现在，图的唯一负循环 E 所在的循环是包含所有顶点的循环（该循环的权重为 -0.00001），因此是哈密顿循环。
非常感谢您的思考！