NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path can also be deduced by recursively traversing dfs.

  • 1
    $\begingroup$ How do you solve Hamiltonian path using a DFS? $\endgroup$ – adrianN Jun 24 '16 at 12:24
  • $\begingroup$ geeksforgeeks.org/find-paths-given-source-destination ..... Use it and check whether the path covers all vertices. $\endgroup$ – Ulsa Minor Jun 24 '16 at 12:26
  • 1
    $\begingroup$ @UlsaMinor And what if it doesn't cover all the vertices? $\endgroup$ – David Richerby Jun 24 '16 at 12:29
  • $\begingroup$ then their is no hamiltonian path available! $\endgroup$ – Ulsa Minor Jun 24 '16 at 12:32
  • 1
    $\begingroup$ @UslaMinor But maybe there is another path that covers all the vertices? You've checked only one possible path. $\endgroup$ – Tom van der Zanden Jun 27 '16 at 7:45

I'm not sure what you mean by "deduced by recursively traversing dfs" but the depth-first search tree is, in general, exponentially large in the size of the graph so any algorithm that potentially involves looking at all of it must take exponential time in the worst case.

Indeed, it's not even obvious that you can solve Hamiltonian path using depth-first search. Consider the graph that is a clique plus one extra vertex, which sends one edge to the clique, say to vertex $x$. If you start your depth-first search at $x$, none of the paths explored by the DFS will be Hamiltonian. Further, if you start at any other vertex in the clique, you might have to explore something like $n!$ paths before you find a path that visits every vertex in the clique, finishing at $x$ and then moves to the extra vertex.

  • $\begingroup$ It's unclear what you mean by depth-first search tree. I know it as the tree produced by DFS. That has the same size as the graph. $\endgroup$ – adrianN Jun 24 '16 at 12:34
  • $\begingroup$ Look at the above link and tell me why you can't use the above and change it a bit to check whether it is hamiltonian path just by adding one case and that is when all the vertices are touched? $\endgroup$ – Ulsa Minor Jun 24 '16 at 12:35
  • $\begingroup$ @UlsaMinor you can do that, but it takes exponential time to check all paths. $\endgroup$ – adrianN Jun 24 '16 at 12:36
  • $\begingroup$ Okay fine, got it. But how do you get the running time for it in exponent? $\endgroup$ – Ulsa Minor Jun 24 '16 at 12:43

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.