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). May 18, 2018 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.

• Sorry, I'm new to graph theory and don't quite get it. A Hamiltonian circuit is a simple cycle that visits each vertex in the graph exactly once. But in the problem I have given, we don't require that. So, I'm just confused on how your stated problem is equivalent to mine.
– user88316
May 10, 2018 at 7:44
• (∩｀-´)⊃━☆ﾟ.*･｡ﾟ reduction... May 10, 2018 at 10:59
• @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, 2018 at 15:50
• @ D.W. - I'm blown by your logic. Just to ensure my understanding is correct, by this reasoning, finding positive cycle of weight n will also be as hard as HAM-CIRCUIT. Isn't it! Sep 17, 2019 at 11:02
• @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, 2019 at 20:21