CODEWITHSUNDEEP
nplongest-path
John Doe
John Doe

Reputation: 123

Proof the longest path is NP-Hard with negative edge weights

I know a similar question has been asked before and that there are abundant amount of resources online, but I have a slightly different question. I understand the reduction from HAM Path to Longest Path. It relies on both needing to use n-1 edges. But what if the graph given in the longest path had a negative edge weight. Then the longest path could have n-2 edges, but HAM would still have n-1 edges.

Is there a different kind of reduction for this problem? Am I missing something?

Upvotes: 1

Views: 338

Answers (1)

templatetypedef
templatetypedef

Reputation: 373082

Here’s an analogy. I want to convince you that Superman has incredible superhuman powers. To do so, I tell you that he’s faster than a speeding bullet. “Faster than a speeding bullet?,” you say. “That’s really fast! No human can do that - it’s really hard!”

Now I tell you more - not only can he run faster than a speeding bullet; he can leap tall buildings in a single jump. “Wow!,” you’d probably say, “that’s also really hard! But then again, I already knew Superman could do really hard things, because you told me he can run faster than a speeding bullet.” In that sense, by saying that Superman can do one hard thing, I’ve already convinced you that he’s pretty strong. Telling you he can also do other hard things doesn’t change that.

Now let’s talk about longest paths. The reason that the longest path problem is NP-hard is that given any graph, you can assign each edge in that graph a length of one, and then check whether that new graph has a simple path of length n - 1. That’s a really hard thing to do, because, as we know, checking for whether a graph has a Hamiltonian path is really hard. (This is the “Superman can run faster than a speeding bullet” bit.)

Now imagine that we say “hey, not only can I solve this problem with positive weights, but I can also solve this problem if the weights are allowed to be negative as well!” From your perspective, I haven’t made the problem of finding longest paths any easier. We can still use the same reduction as before to find Hamiltonian paths. It’s just also the case that we can do other things as well. (This is the “can leap tall buildings in a single jump” bit.)

In general, if you start with an NP-hard problem and then generalize it, you’re usually left with an NP-hard problem because that problem still has all the hard bits from before, plus a bunch of new cases it needs to handle as well.

Upvotes: 0

Related Questions