5
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\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
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.