# How is the Longest Path Problem NP complete?

https://www.csie.ntu.edu.tw/~lyuu/complexity/2016/20161129s.pdf So basically, in our iff proof, we have to show two directions:

Forward: If Hamiltonian Path has a yes-instance, so does longest path. This makes sense because we can just let "k" = |V| - 1 if hamiltonian path is yes. Then clearly there is a longest simple path with |V| - 1 edges.

I'm having trouble with the backward part

Backward: If Longest Path has a yes instance, so does longest path. Let's assume that there is a longest path from s to t of length k (this can be a different k than the one we defined above?). How does that guarantee that there is a hamiltonian path from s-t? If it is the same k, where k = |V| - 1, then I agree there is a hamiltonian path, but what if this k is something different?

It doesn't, but the Longest Path problem doesn't require a path between particular vertices, it only requires that some simple path of length $$K$$ exist in the graph. To reduce Hamiltonian Path to Longest Path you just require that path to have $$|V| - 1$$ edges, which in a simple path must involve all the vertices in the graph, making it a Hamiltonian Path.