使用贝尔曼福特来检测产品超过阈值的循环

该图有2个周期。一个产品= 1，另一个产品= 4。如果阈值= 1，算法应该输出为真，因为有一个产品> 1的周期。

我假设你想检测一个重量超过某个阈值的简单周期（否则，你可以重复任何正面权重>超过任何肯定的阈值）。

不幸的是，这个问题是 NP-Hard 。

从 G =（V，E）哈密尔顿周期问题，保持同样的图 G ，其中 w（e）= 2 边缘，然后将它发送到阈值 2 ^ | V | -1 的问题。 如果任何周期的权重大于 2 ^ | V | -1，那么它的边数多于 | V | -1`所以这个循环是哈密尔顿算子，如果有一个哈密尔顿循环，算法会发现有一个重量为2 * 2 * ... * 2> 2 ^ | V | -1的循环。

由于哈密尔顿周期是Np-完全的，并且我们找到了这个问题的多项式约化，所以这个问题是NP-Hard，并且没有已知的多项式解。

Bellman Ford is used to detect negative weighted cycles in a graph. I would like to know how I can use it to detect cycles which exceeds a certain threshold instead.

Example:

This graph has 2 cycles. One with the product = 1 and the other with the product = 4. If the threshold = 1, the algorithm should output true, since there is 1 cycle with a product > 1.

I assume you want to detect a simple cycle with weight that exceeds some threshold (otherwise, you can repeat any positive weight>1 cycle enough times to exceed any positive threshold).

Unfortunately, that problem is NP-Hard.

A simple reduction from the Hamiltonian cycle problem:

Given an instance G=(V,E) of Hamiltonian cycle problem, keep the same graph G, with w(e) = 2 for any edge, and send it to the problem with threshold 2^|V|-1. If there is any cycle with weight bigger than 2^|V|-1, then it has more than|V|-1` edges, so this cycle is hamiltonian, and if there is a hamiltonian cycle, the algorithm will find that there is a cycle of weight 2*2*...*2> 2^|V|-1.

Since Hamiltonian Cycle is Np-Complete, and we found polynomial reduction from it to this problem, this problem is NP-Hard, and there is no known polynomial solution to it.

tl;dr: to use Bellman Ford to solve this problem, is far from trivial, and if possible, will require modifying the graph to be exponential in size of the original graph (Assuming P!=NP)