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

Leave a Reply