Longest Path
We have a graph G=(V,E), lengths l(e) in Z^(+) for each e in E, a positive integer K and two nodes s,t in V.
The question is if there is a simple path in G from s to t of length at least K ?
- Show that the problem Longest Path belongs to NP.
- Show that the problem Longest Path is NP-complete, reducing Hamiltonian Path to it.
- Show that if the graph is directed and acyclic then the problem can be solved in time O(|V|+|E|).
Could you give me a hint how we could show that the problem belongs to NP? Also, how can we reduce a problem to an other, in order to show that the latter is NP-complete?
EDIT:
So in order to show that the problem belongs to NP, do we have to draw a simple and count the sum of the lengths of the edges?
Do we say for example the following?
We see that the length of the path from the node s to the node t is equal to l((s,w))+l((w,t))=3+12=15, so there is no simple path in G from s to t of length at least K.
Or does it suffice the following?
"Given a a simple path , we can easily check if its length is at least K(by simply computing the sum of lengths of all edges in it). Thus, it is in NP."
EDIT 2: Also could you explain me further why we reduce the Hamiltonian path problem to this one in polynomial time by setting all edges' lengths equal to one and set K = |V| - 1 ?
EDIT 3: Suppose that we have a problem A and a problem B and it is known that B is NP-complete. If we want to show that A is also NP-complete, do we change the data of A in that way so that we have the same problem as the problem B and so we deduce that A is also NP-complete? Or have I understood it wrong?
EDIT 4: Also how can we show that if the graph is directed and acyclic then the problem can be solved in time O(|V|+|E|)?
EDIT 5: All edges'lengths of a Hamiltonian path are equal to 1, right? And if we have V vertices, the length of the longest path is at V-1, yes? But in our problems, the lengths of the edges aren't specific and K is also not a fixed number. So if we set all edges' lengths equal to one and set K = |V| - 1, don't we reduce our problem to the Hamiltonian path problem? Or have I understood it wrong?