236. How can you decide whether a DAG has a Hamiltonian path in linear time?
MediumGraph algorithms
Technical
Show model answer
Compute a topological order. A Hamiltonian path in a DAG must visit vertices in a topological order, and if it exists that order is forced. So the DAG has a Hamiltonian path iff every pair of consecutive vertices in the topological order is joined by an edge.
That check costs O(V + E). It is the same condition as the topological order being unique. In general graphs, by contrast, the Hamiltonian path problem is NP-complete.