# Finding the lowest-weight negative cycle in a weighted digraph

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?

• 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? – Yuval Filmus Mar 23 '16 at 16:09
• $-2$. And I'm interested in simple cycles! – Nikhil Mar 23 '16 at 16:12
• I meant $-2$ is the lesser weight among the two. – Nikhil Mar 23 '16 at 17:44
• 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. – 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.