1
$\begingroup$

From the following link:

https://www.csie.ntu.edu.tw/~lyuu/complexity/2016/20161129s.pdf

enter image description here

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?

$\endgroup$
2
$\begingroup$

How does that guarantee that there is a hamiltonian path from s-t?

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.

$\endgroup$
0
$\begingroup$

Remember that we want to reduce Hamilton path problem to the longest path problem. Hence we have to show that an instance I of Hamilton path problem has a Hamilton path if and only if its transformed instance f(I) has a longest path of length n-1 where f is the reduction. We don't have to care about longest path problem instances where k is something different.

To make the point clearer, you could show the correctness of the reduction in a slightly different way: Show that if G has a Hamilton path, then G has a path of length n - 1. And if G has no Hamilton path, then G has no path of length n - 1.

$\endgroup$
0
$\begingroup$

I agree with @Kyle Jones; and the 'iff' part in the proof looks little fishy to me. For the NP-Hard part, you may refer to my answer here https://cs.stackexchange.com/a/137129/62634 - I've tried to prove it from the basics.

For the 1st part, to prove that the longest path is NP, I was thinking to start off with guessing a path of size K=|V| -1 and then check in polynomial time whether it exists/simple-path. If not, then I guess again a path of size K-1, and do the test, and this goes on until k=1. This way I have to guess only |V|-1 time. By contrast, the proof that you've cited, could also mean that there are exponential number of paths of size between size K and |V|-1.

$\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.