2
$\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?

$\endgroup$
  • 2
    $\begingroup$ Do you have to reduce from SAT? A simple reduction is from Hamiltonian path. $\endgroup$ – Juho Jun 2 '19 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 '19 at 18:33
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.

$\endgroup$

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.