3
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Do you have to reduce from SAT? A simple reduction is from Hamiltonian path. $\endgroup$
    – Juho
    Jun 2, 2019 at 11:02
  • $\begingroup$ The decision version of your problem is: Given a graph and a number $\ell$, is there a path whose length is shorter than $\ell$? This is clearly in NP. $\endgroup$
    – Yuval Filmus
    Jun 2, 2019 at 18:33

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
1

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.