The following is a Yes/No question. In an undirected unweighted graph $G$, a longest path between two given vertices $s$ and $t$ can be found using Depth-first search?

If it is possible to use DFS to find such a path, show the algorithm.

My thoughts: My answer is Yes. I would solve it by brute force using backtracking, my DFS. And the class of the graph doesn't really matter here. Am I right?

  • 2
    $\begingroup$ Why do you think that DFS can find a longest path? What do you mean by "how could it be the algorithm"? I'm having a hard time understanding what you are asking. I encourage you to edit the question to provide more context/motivation, explain what your question is, and tell us what your thoughts are. $\endgroup$ – D.W. Sep 23 '18 at 23:59
  • $\begingroup$ Is it better now? I $\endgroup$ – jonaprieto Sep 24 '18 at 7:30
  • $\begingroup$ Hint: what would this imply for P vs NP? $\endgroup$ – Peter Taylor Sep 24 '18 at 13:44
  • $\begingroup$ What do you mean by 'longest path'? If you mean the common definition, then as @Peter indicated, the wikipedia item tells us the problem to find the longest path between two vertices is NP-complete. $\endgroup$ – Apass.Jack Sep 25 '18 at 5:40

Your Answer

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

Browse other questions tagged or ask your own question.