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?
Asked By : omega
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10732
Answered By : Luke Mathieson
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.
