# Is it possible to detect a simple negative-weight cycle of weight $N$ in polynomial time?

Given a directed graph and an integer $N$, is it possible to detect a simple negative-weight cycle whose edges sum to $N$ in polynomial time? I thought about modifying the Floyd-Warshall algorithm to check if the diagonals equal $N$ as they get set, but I realized this wouldn't work if a vertex appeared in multiple negative-weight cycles.

• It is possible to modify Floyd-Warshall so that, even with an input graph containing negative weight cycles, all of the off diagonal entries will not contain any cycles, and the diagonal entries $i\to i$ will not contain any smaller cycles besides one traversal of the large cycle $i\to i$. But Floyd-Warshall will only find the smallest (or largest) cycle $i\to i$ for each vertex $i$. Thus you could deduce in polynomial time, for each $i$, whether the number $N$ is between the two numbers weight(smallest cycle i->i) and weight(largest cycle i->i). – Jasha May 18 '18 at 23:58

No, there isn't (not unless P=NP). Take an unweighted directed graph on $n$ vertices, and set all of the edge weights to $-1$. Now there is a simple cycle of weight $-n$ if and only if there is a Hamiltonian circuit in the original graph. But detecting the existence of Hamiltonian circuits is NP-hard. Therefore your problem is NP-hard, too.
• @Jake, when I ask for the weight of the cycle to be $-n$, where $n$ is the number of vertices, that does effectively require that each vertex be visited exactly once. – D.W. May 10 '18 at 15:50
• @KGhatak, If there is a flaw in the logic, I'd be interested to hear where it is. By this logic, finding a simple positive cycle of weight $n$ will also be as HAM-CIRCUIT. I believe that is correct. Note that the "simple" part is essential. – D.W. Sep 17 at 20:21