I was trying to find all the negative cycle vertices using the Bellman–Ford algorithm using this paper solution 7.1(b) in $O(V)$ by tracing back the predecessor subgraph.It is also stated in this answer too. But then while googling I found another Stack Overflow question it is proved that finding negative cycle vertices are NP complete. So what is it actually?


Your question is very unclear.

There is a tremendous difference between: (a) print out one example of a negative cycle, if one exists, (b) print out all negative cycles.

The former can be done in polynomial time using Bellman-Ford. The latter cannot, as there could be exponentially many cycles, so it could take exponential time. (The latter is not NP-complete, as the problem is not even in NP.)

The solution you link to is solving problem (a).


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.