6
$\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?

$\endgroup$
4
  • $\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$ Commented Mar 23, 2016 at 16:09
  • $\begingroup$ $-2$. And I'm interested in simple cycles! $\endgroup$
    – Nikhil
    Commented Mar 23, 2016 at 16:12
  • $\begingroup$ I meant $-2$ is the lesser weight among the two. $\endgroup$
    – Nikhil
    Commented Mar 23, 2016 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$ Commented Mar 23, 2016 at 17:48

1 Answer 1

4
$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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