4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ is the longest path as you quoted required to be simple or not? $\endgroup$ – Charlie Parker Apr 29 '16 at 2:40
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ just to make sure, so the last question about visiting specific vertex - it would also be NP-complete, right? $\endgroup$ – Zat Mack Jul 9 '12 at 23:53
  • $\begingroup$ @ZatMack Yes, it would. $\endgroup$ – Juho Jul 10 '12 at 0:27
  • $\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 Mack Jul 10 '12 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$ – Juho Jul 10 '12 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 Mack Jul 10 '12 at 12:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.