how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph?

Question

I can use Bellman-Ford to get some of the elementary negative weight cycles in a graph. It's not guaranteed to always get all of them.

(Elementary Cycle: A cycle is elementary if no vertex but the first and last appears twice.)

But I want to find ALL elementary negative weight cycles. Even taking each vertex as the source will not always get ALL negative weight cycles.

Take this graph for example:

With Bellman-Ford, starting from any vertex, I can only get one cycle "U→H→U".

The cycle "U→S→U" is always missing.

Is there any algorithm with which I can find all negative weight cycles reliably?

(I needed three attempts to understand $A$ until I concluded that you probably want to emphasise exactly one.) If there is more than one negative weight cycle, what is the elementary circuit? — greybeard, Oct 4, 2020 at 21:08
@greybeard Thanks for your comments. How about this version? Is it more clear now? — Long Bu, Oct 5, 2020 at 1:21
You might get a lot of cycles: for example in a complete graph on $n$ vertices, where all edge weights are negative, you would get something like $n!$ elementary cycles. Do you want to impose some kind of disjointness condition on the output cycles? — Joppy, Oct 6, 2020 at 11:03

Long Bu · Accepted Answer · 2020-10-06 16:06:18Z

1

My current strategy is:

first enumerate all elementary cycles. I use the hawick algorithm which is already implemented in the c++ boost library.
sum all the weights of edges in each cycle and then check if the sum is negative.

answered Oct 6, 2020 at 16:06

Long Bu

1313 bronze badges

Add a comment |

1 Answer 1