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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ is the longest path as you quoted required to be simple or not? $\endgroup$– Charlie ParkerCommented Apr 29, 2016 at 2:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
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.
-
$\begingroup$ just to make sure, so the last question about visiting specific vertex - it would also be NP-complete, right? $\endgroup$– Zat MackCommented Jul 9, 2012 at 23:53
-
-
$\begingroup$ Sorry for disturbing, but what about this case: we define a starting vertex of a ham/line path and an end vertex of a ham/line path, and define one specific vertex that the ham/line path has to reach. would determining this still be NPC? $\endgroup$– Zat MackCommented Jul 10, 2012 at 3:29
-
$\begingroup$ @ZatMack It clearly doesn't make the problem any easier. Try to think of the worst possible case: if you could efficiently solve what you suggest, then you could solve the Hamiltonian path problem efficiently as well. In the future if you want to understand things instead of guessing, I'd suggest picking up e.g. Sipser's book. $\endgroup$– JuhoCommented Jul 10, 2012 at 12:11
-
$\begingroup$ I know that it'll not make the problem any easier; I wanted to know whether it'd make the problem much harder. $\endgroup$– Zat MackCommented Jul 10, 2012 at 12:13