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

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.