How to prove NP-hardness of a longest-path problem?

Question

I have this question:

Input: 
G(V, E) = an undirected graph, V={v1, v2, ..., vn} (V = set of nodes, E = set of edges)
where there is a path connecting from v1 to vn.

Question: 
What is the maximum number of nodes you can visit when starting from v1 and ending at vn. 
(including v1 and vn) 
Each node can only be visited at most once.

I want to prove that this is NP-hard by reducing it from a known NP-complete problem, such as undirected Hamiltonian path or subset-sum.

However I don't know exactly how to do this and this is where I need help.

Can anyone help please?

Answer 1

Assuming I understand your definition, your problem is related to the optimisation version of LONGEST PATH:

LONGEST PATH
Input: A graph $G=(V,E)$, an integer $k$.
Question: Is there a path with at least $k$ vertices in $G$

This problem is NP-complete, there's a fairly obvious reduction from HAMILTONIAN PATH - just set $k = n$, and clearly if we are given an (ordered) set of vertices, we can easily check that it is a path over at least $k$ vertices.

Note that we can assume that $G$ is connected, and we will do so from now on.

The optimization version max-LONGEST PATH where we ask for the path of maximum length is then NP-hard (the polynomial-time equivalence of these two problems is a straightforward exercise).

Then the difference between max-LONGEST PATH and your problem is that you have two specified vertices that are the start and the end of the path. Now we need a reduction from some NP-hard problem to your problem, but we already have one that's really close.

Given an instance $G$ of max-LONGEST PATH you should now be able to construct an instance $G'$ of your problem such that if $p$ is the longest path in $G$, then this is almost the longest path in $G'$.

A further hint if you are still beating your head against a wall in about, say, 2 hours:

Try taking $G$ and adding two new vertices $s$ and $t$ and connecting them so that they can start and end such a path $p$ - remember though that you don't know what $p$ is.

Answer 2

Suppose we have a solution to the longest path problem, longest-path, in which given a graph G, and an integer k, we need to decide if G has any (simple) path of k edges. Then to solve the Hamiltonian-path problem, HAM-PATH, we could use longest-path with k=|G|-1. This means, HAM-PATH is polynomial time reducible to longest-path. $$\begin{aligned} i.e., HAMPATH \le_{p} longest \text{ - } path \\ equivalently,\hspace{15px} longest \text{ - } path \in P \Longrightarrow HAMPATH \in P \\ taking \hspace{5px} contrapositive, \hspace{15px} HAMPATH \not\in P \Longrightarrow longest \text{ - } path \not\in P \\ \end{aligned}$$

Since HAM-PATH is NP-Hard, so is longest path problem. However, it should be noted that for certain types of graphs, polynomial time solutions exist.