HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Finding the lowest-weight negative cycle in a weighted digraph

Submitted by: @import:stackexchange-cs··
0
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?

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.