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$
1
  • $\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, 2018 at 23:58

1 Answer 1

5
$\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$
7
  • $\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$
    – user88316
    May 10, 2018 at 7:44
  • 2
    $\begingroup$ (∩`-´)⊃━☆゚.*・。゚ reduction... $\endgroup$ May 10, 2018 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, 2018 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, 2019 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, 2019 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.