Algorithm for finding a Hamiltonian Path in a DAG

Question

I am referring to Skienna's Book on Algorithms.

The problem of testing whether a graph G contains a Hamiltonian path is NP-hard, where a Hamiltonian path P is a path that visits each vertex exactly once. There does not have to be an edge in G from the ending vertex to the starting vertex of P , unlike in the Hamiltonian cycle problem.

Given a directed acyclic graph G (DAG), give an O(n + m) time algorithm to test whether or not it contains a Hamiltonian path.

My approach,

I am planning to use DFS and Topological sorting. But I didn't know how to connect the two concepts in solving the problem. How can a topological sort be used to determine the solution.

Any suggestions?

Answer 1

You can first topologically sort the DAG (every DAG can be topologically sorted) in O(n+m).

Once this is done, you know that edge go from lower index vertices to higher. This means that there exists a Hamiltonian path if and only if there are edge between consecutive vertices, e.g.

(1,2), (2,3), ..., (n-1,n).

(This is because in a Hamiltonian path you can't "go back" and yet you have to visit all, so the only way is to "not skip")

You can check this condition in O(n).

Thus, the overall complexity is O(m+n).