Is longest possibly non-simple path in NP?

Question

I know that the following problem is in NP-HARD: Given a simple graph G=(V,E), two vertices v, v' in V, an integer B, and a non-negative length function len: E-> Z+, is there a simple path from v to v' with length less than B?

My question is: Given the same conditions as before, if we are interested in finding the longest not necessarily simple path in G from vertex v to v', is the problem still in NP-HARD?

Note: I've tried to reduce hamilton-path to it, but I'm still not able to prove whether there's a problem in NP reducible to this one I'm mentioning. I've also looked up in Garey & Johnson but I haven't found anything.

I would please like a little hint to prove if this problem is NP-HARD. Thanks in advance!

Answer 1

No, it's not NP-hard; you can use a shortest path algorithm (such as Bellman-Ford) to solve it in polynomial time by negating your edge lengths. Note that it is likely that the longest path will be infinite, particularly when all edge weights are non-negative.

Answer 2

Shortest simple path in a graph without negative cycles is not NP-hard. See Cormen 'An Introduction to Algorithms'. It can be solved using Bellman-Ford's Algorithm. If we have no negative edge weights one can also use Dijkstra's Algorithm. Both calculate all shortest path from a single source to all other nodes of a graph. So your first problem, as I understand you correctly, is not NP-hard.

Longest simple path problem, given that no positive cycles exist, is the dual of the shortest simple path problem with no negative cycles. Also not NP-hard.

Shortest (not-simple) path, allowing negative cycles, is NP-hard, because you need to remember all possible paths to a node, and that can be exponential. Same should be true for a Longest (not-simple) path problem, where positive cycles are allowed.

I hope that answers your question.

If I missed anything or any statement is wrong, please feel free to correct me.