Is finding the longest path of a graph NP-complete?

Answered By : Juho

First, it is easy to see that the problem is in $\text{NP}$. The longest path is a Hamiltonian one since it visits all vertices. Indeed, there is a straightforward reduction from $\text{HAM-PATH}$ to it. For details and some special cases, see for example here. Likewise, it is $\text{NP}$-complete to decide whether there is a path of length $k$ with the a similar argument: just set $k$ such that the problem is equivalent of solving $\text{HAM-PATH}$. Finally, if I understood your third point correctly, it doesn't make the problem any easier if you in addition require the path to visit a specific vertex $v$. Similar reasoning holds for this case.

Problem Detail: 

The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of a graph NP-complete? Is it still NP-complete if we require the path to visit a given vertex?

Asked By : Zat Mack

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/2660