In the longest path problem, given a weighted graph G and a starting node v0, find the simple path starting with v0 with the largest sum of weights.
Show that the longest path problem is NP-hard in general. Assume an efficient algorithm to solve the longest path and show how an efficient algorithm which decides the existence of a Hamiltonian path can be derived from that.
Please help :( Thank you!
The main method to show a problem is NP-hard is via the process of reduction. Reduction means taking some unknown problem $p$, and showing that if you had a way to solve $p$ in polynomial time, then you can solve a known NP-hard problem $q$ in polynomial time.
You are given the fact that the problem Hamiltonian Path is NP-hard already (so it's our $q$ in this case). The goal is to show that the longest path problem (which is our $p$) is harder than the Hamiltonian Path problem. You can do this by finding an instance of the longest path problem, which when solved, also solves the Hamiltonian Path problem.
Here's a framework for the proof of this problem. Your job is to figure out what $G'$, the weights of each edge, and $W$ should be.
Let $G = (V,E)$ be a graph, and $v_{0} \in V$. We want to know if $G$ has a Hamiltonian path starting from $v_{0}$. Create a graph $G' = (V', E')$ with weights (INSERT WEIGHTS HERE). Now suppose $G'$ has a longest path of total weight $W$. Then G (DOES / DOES NOT) have a Hamiltonian path, because (REASON). This shows that Longest Path reduces to Hamiltonian Path, and hence the former is NP-hard.
Note that there are two cases you have to cover for: $G$ does or does not have a Hamiltonian path, and in the positive case, you do have to explain how to "convert" the longest path in $G'$ to the Hamiltonian path in $G$.
Hint: $G'$ is not too different from $G$. Good luck!