patternMinor
Finding the lowest-weight negative cycle in a weighted digraph
Viewed 0 times
cyclethedigraphlowestweightedweightfindingnegative
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#54829, answer score: 4
Revisions (0)
No revisions yet.