Mark
Mark

Reputation: 47

How a shortest path problem with negative cost cycles can be polynomially reduced to the Hamiltonian cycle problem to demonstrate NP-completeness

I know that if there are negative cost cycles in a graph, the relative shortest path problem belongs to the np-complete class. I need to prove this by performing a polynomial reduction using the Hamiltonian cycle problem. Could anyone explain it? It would be very helpful.

Upvotes: 0

Views: 527

Answers (0)

Related Questions