查找包含所有负周期的最低子图 [英] Finding the minimal subgraph that contains all negative cycles

问题描述

我被困在下面的问题：给定一个加权图G，我想构造G的最小的子图，它包含的G全部阴性（简单的）周期

I'm stuck at the following problem: Given a weighted digraph G, I'd like to construct the minimal subgraph of G that contains all negative (simple) cycles of G.

我不知道如何找到使用贝尔曼 - 福特负周期，我知道简单的循环有向图的数量指数。

I do know how to find a negative cycle using Bellman-Ford, and I know that the number of simple cycles in a directed graph is exponential.

一个幼稚的方式来解决这个问题的办法是简单地遍历所有的简单循环，并挑选那些消极的，但我有一种感觉，那可能是一个多项式时间的算法。我通过谷歌发现大多数文章是关于寻找一个（而不是全部）不良的循环。

One naive way to approach the problem would be to simply iterate all simple cycles and pick those that are negative, but I have the feeling that there might be a polynomial-time algorithm. Most articles that I found through Google were about finding a (rather than all) negative cycle.

我希望能找到一些专家在这里计算器，可以给出一些提示建立一个多项式时间的解决方案，或暗示对证明不能在多项式时间内解决。

I'm hoping to find some experts here on stackoverflow that may give some hints towards a polynomial-time solution, or hints towards proving that it can't be solved in polynomial time.

提前感谢！

干杯，罗伯特·

推荐答案

对于有兴趣的人还是停留在一个类似的问题：它的NP完全问题。感谢至极指着我的cstheory线程。

For anyone interested in or stuck at a similar problem: it's NP-complete. Thanks to wich for pointing me to the thread in cstheory.

要了解为什么它的NP完全问题，首先观察到的问题可能是表述如下：给定一个加权有向图G有N verices和G上边缘E，找出数E是否位于一个（简单）不良的循环。如果是这样，E应该在子图H.如果不，它不应该在H中。

To see why it's NP-complete, first of all observe that the problem may be stated as follows: given a weighted directed graph G with N verices and an edge E on G, find out whether E lies on a (simple) negative cycle. If it does, E should be in the subgraph H. If it does not, it should not be in H.

现在，让我们边E为E =（U，V）与重量瓦特我们想知道是否有从V路径到u，总重量W，使得W + W＆LT; 0。如果我们能在多项式时间内做到这一点，我们也可以解决在多项式时间汉密尔顿的周期问题：

Now, let edge E be E = (u, v) with weight w. We'd like to know whether there's a path from v to u with total weight W such that W + w < 0. If we could do this in polynomial time, we could also solve the Hamiltonian Cycle problem in polynomial time:

分配给边E的N重 - 1.00001。分配给在图中的-1的重所有其它边缘。现在，图形的唯一负循环的其中E所在，是一个包含所有顶点（即周期有重量-0.00001），因此是一个汉密尔顿的周期，周期

Assign to edge E a weight of N - 1.00001. Assign to all other edges in the graph a weight of -1. Now the graph's only negative cycle on which E lies, is the cycle that contains all vertices (that cycle has weight -0.00001) and is thus a Hamiltonian Cycle.

非常感谢一起思考！

这篇关于查找包含所有负周期的最低子图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！