0

I'm trying to design an algorithm that runs in O(n+m) time, to determine if a Hamiltonian path exists in a given directed acyclic graph.

Here is an algorithm for this problem:

Perform a topological sort of the DAG, then check if successive vertices in the sort are connected in the graph. If so, the topological sort gives a Hamiltonian path. On the other hand, if there is a Hamiltonian path, then the path gives a topological sort of the DAG.

Now I don't know how to prove its correctness and find out its space complexity. Any help would be appreciated.

Andromeda
  • 49
  • 1
  • 12
  • 1
    I found an answer on a similar question https://stackoverflow.com/questions/16124844/algorithm-for-finding-a-hamilton-path-in-a-dag But I feel unconfortable with the fact that different topological sorts are possible. – Vince Dec 12 '18 at 13:36
  • @Vince I saw that, but my problem is the proof of its correctness and its space complexity that weren't mentioned there. – Andromeda Dec 12 '18 at 13:57
  • You should move your question to [https://cs.stackexchange.com/](https://cs.stackexchange.com/) – Guy Coder Dec 12 '18 at 14:03
  • Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [On topic](http://stackoverflow.com/help/on-topic), [how to ask](http://stackoverflow.com/help/how-to-ask), and [... the perfect question](https://codeblog.jonskeet.uk/2010/08/29/writing-the-perfect-question/) apply here. StackOverflow is not a design, coding, research, or tutorial resource. – Prune Dec 12 '18 at 16:52
  • ["Can Someone Help Me?" is not a valid SO question](https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question). This usually suggests that what you need is time with a local tutor or walk through a tutorial, rather than Stack Overflow. – Prune Dec 12 '18 at 16:52
  • Please check ["Which site?"](https://meta.stackexchange.com/questions/129598/which-computer-science-programming-stack-exchange-do-i-post-in) – Prune Dec 12 '18 at 16:53

1 Answers1

0

Actually, you have very nearly proved it yourself. The missing part of your proof is to show that if the DAG has a Hamiltonian path, then the topological sorting algorithm must find it, because there is no other way to put the nodes in a topological-sorted order:

Suppose there is a Hamiltonian path. Let u and v be any two nodes, and suppose without loss of generality that u occurs before v in the Hamiltonian path. Then there is a path from u to v formed from the nodes in the Hamiltonian path between u and v, so u must occur before v in any topological-sorted order.

It follows that all pairs of nodes in a topological-sorted order have the same relative ordering as they have in the Hamiltonian path. Therefore, if the nodes are topologically sorted then they are in the same order as the Hamiltonian path.

Therefore, if there is a Hamiltonian path, running any topological sorting algorithm will find it. The inverse is rather trivial; if there is no Hamiltonian path then of course topological sorting won't find one.

Regarding space complexity, this will be the same as the space complexity of your topological sorting algorithm, because the second stage where you check if the result is a Hamiltonian path takes O(1) extra space. The space complexity of standard topological sorting algorithms is O(n) where n is the number of vertices.

kaya3
  • 47,440
  • 4
  • 68
  • 97