Algorithm for finding a Hamilton 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

I don't think the statement by @agassaa is entirely correct. Consider the simple example where there are three nodes "A", "B", "C", and edges A->B, B->C, A->C. While A has two children and C has two parents, A->B->C forms a Hamiltonian path. You don't need to traverse every edge in the graph for the path to be Hamiltonian.

A DAG that has Hamiltonian cycle

Answer 2

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).