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:
--------->
^ |1
0.5 | <------v
1 -----------> 2
^ |
|4 |1
| 2 v
4<------------3
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)
Partial Solution to the problem
This solution is working, whenever the threshold is equal to 1.
tl;dr Change weights of edges, by applying logarithm and use Floyd-Warshal to detect negative cycles, which will occur, if the product of the original weights of a cycle is greater than 1.
long answer.
Floyd-Warshal can be used for APSP, as well as detecting negative cycles in a graph. To make this problem a problem, were the solution involves finding neg. cycles, do the following:
- Build a graph, based on a adjacency matrix
- init the values of the matrix with the
log(weight of edge) * (-1)
This value will become positive, if the original value is smaller than 1, or in other words: It is negative for all values greater than 1.
Since log(m * n) = log(m) * log(n), we do not have to multiply anymore to get the result, but simply add the logs.
Therefore, if the algorithm found a negative cycle, we can know that the products it`s edges from the original cycle is greater than 1.
