2
$\begingroup$

Given a weighted digraph with positive and negative edge weights, what is the complexity of finding the shortest (uses the least number of edges) negative weight cycle in the graph?

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?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Do you consider a cycle of length 2 a simple cycle? $\endgroup$ – Yuval Filmus Mar 23 '16 at 18:51
3
$\begingroup$

You can use dynamic programming (in this case, known as the Floyd–Warshall algorithm) to calculate the least weight of a walk of length $\ell$ from $x$ to $y$, for all vertices $x,y$ and $\ell \geq 0$. The first $\ell$ (if any) such that this weight is negative is the length of the shortest negative cycle. (This breaks if there are bidirectional negative edges, unless you consider them as simple cycles.)

Improve this answer
$\endgroup$
3
  • $\begingroup$ But Floyd–Warshall calculate the least weight of a walk only with the vertices {1,2,...,ℓ}, not the least weight of a walk with length ℓ. $\endgroup$ – Tomer Wolberg Jan 5 '19 at 18:39
  • $\begingroup$ You’re right, I meant some other algorithm. Perhaps Bellman-Ford? $\endgroup$ – Yuval Filmus Jan 5 '19 at 18:46
  • $\begingroup$ You can use Bellman Ford but you would need to run it from each vertex. $\endgroup$ – Tomer Wolberg Jan 6 '19 at 16:04

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.