Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the negative cycle in the graph whose weight is as small as possible?

I know that I can detect negative weight cycles using Bellman-Ford. Has this variation be studied before? Can you point me to a reference?

  • $\begingroup$ When you say least weight, do you mean minimal or maximal weight? That is, if there were cycles of total weight $-1$ and $-2$, which is the one with the lesser weight? $\endgroup$ – Yuval Filmus Mar 23 '16 at 16:09
  • $\begingroup$ $-2$. And I'm interested in simple cycles! $\endgroup$ – Nikhil Mar 23 '16 at 16:12
  • $\begingroup$ I meant $-2$ is the lesser weight among the two. $\endgroup$ – Nikhil Mar 23 '16 at 17:44
  • 1
    $\begingroup$ The usual rule is one question per post. I only answered your first question. If you're interested in the other one as well, please ask it separately. $\endgroup$ – Yuval Filmus Mar 23 '16 at 17:48

Finding the least weight simple negative cycle is NP-hard even in the undirected case, as shown in this answer by reduction from Hamiltonicity. The reduction is very simple: make each edge have weight $-1$. There is a cycle of least weight at most $-n$ iff the graph is Hamiltonian.


Your Answer

