3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Jasha May 18 '18 at 23:58
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jake May 10 '18 at 7:44
  • 2
    $\begingroup$ (∩`-´)⊃━☆゚.*・。゚ reduction... $\endgroup$ – Panos Kal. May 10 '18 at 10:59
  • $\begingroup$ @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. $\endgroup$ – D.W. May 10 '18 at 15:50
  • $\begingroup$ @ 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! $\endgroup$ – KGhatak Sep 17 at 11:02
  • $\begingroup$ @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. $\endgroup$ – D.W. Sep 17 at 20:21

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.