I am trying to find the path for the most negative cycle in a graph G which starts and ends at a specified source node S.

I have studied an application/ extension of the Bellman-Ford algorithm (henceforth referred to as the "Huang algorithm") found here which describes how to find a negative cycle reachable from a specified node. However, this does not ensure that the "full cycle" going from S -> cycle -> S is negative.

Here is my current research into this topic:

On the nth iteration of the Bellman Ford algorithm, if an edge can be relaxed, then the graph contains a negative cycle. Using the Huang algorithm I can retrace the path of the negative cycle through the predecessor dictionary until a vertex repeats. When a vertex repeats, I cease iterating over the predecessor and now have my path for the negative cycle. However, the source vertex is often not in this path. I believe it is also sometimes not the most negatively-weighted path.

I would like to find the most negative cycle of which S is a part. (This can include a cycle with a subcycle detected by the Huang algorithm)

  • $\begingroup$ Are you looking for a simple cycle? (i.e., no vertex is repeated) Otherwise, you can always find a cycle that is more negative by just traversing the cycle multiple times. $\endgroup$ – D.W. Feb 28 '18 at 4:55
  • $\begingroup$ If so, I think it's NP-hard, by reduction from the longest-path problem; see cs.stackexchange.com/a/83673/755. $\endgroup$ – D.W. Feb 28 '18 at 4:58
  • $\begingroup$ I am looking for the most negative cycle where no edges repeat. $\endgroup$ – BlueOxile Feb 28 '18 at 16:02
  • $\begingroup$ Please edit the question to specify that in the question, so people don't have to read the comments to understand what you are asking. Thank you! $\endgroup$ – D.W. Feb 28 '18 at 16:51
  • $\begingroup$ I suggest trying to prove it is NP-hard by reduction from the longest-path problem, by constructing the dual graph (replace each edge with a vertex and each vertex with an edge). Does that lead to a working reduction? $\endgroup$ – D.W. Feb 28 '18 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.