patternMinor
Proof that shortest path with negative cycles is NP hard
Viewed 0 times
pathshortestwithhardthatnegativecyclesproof
Problem
I'm looking into the shortest path problem and am wondering how to prove that shortest path with neg. cycles is NP-hard. (Or is it NPC? Is there a way to validate in P time that the path really is shortest?)
How would I reduce the SAT problem into the shortest path problem in polynomial time?
How would I reduce the SAT problem into the shortest path problem in polynomial time?
Solution
Copied from my answer on cstheory.stackexchange.com:
Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.
This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.
Thus your problem is NP-Hard.
Paths with no repeated vertices are called simple-paths, so you are looking for the shortest simple-path in a graph with negative-cycles.
This can be reduced from the longest-path problem. If there were a fast solver for your problem, then given a graph with only positive edge-weights, negating all the edge-weights and running your solver would give the longest path in the original graph.
Thus your problem is NP-Hard.
Context
StackExchange Computer Science Q#110147, answer score: 5
Revisions (0)
No revisions yet.