Detecting Hamiltonian path in a graph There are various methods to detect hamiltonian path in a graph.


Brute force approach. i.e. considering all permutations T(n)=O(n*n!)
Backtracking T(n)=O(n!)
Using Dynamic programming T(n)=O(2^n * n^2)


Now, there is one another method using topological sort. Topological sort has an
interesting property: that if all pairs of consecutive vertices in the sorted order are connected by
edges, then these edges form a directed Hamiltonian path in the DAG. If a Hamiltonian path
exists, the topological sort order is unique. Also, if a topological sort does not form a
Hamiltonian path, the DAG will have two or more topological orderings.

Approximation Algorithm: Compute a topological sort and check if there is an edge between each
consecutive pair of vertices in the topological order.

I have a doubt that why is it considered as an approximate algorithm? Wouldn't it give correct output every time? What are the cases when it won't give correct output?
Hamiltonian Path in a DAG is easy to solve: You can find the longest path in $O(|V|+|E|)$ time using the critical path algorithm: https://en.wikipedia.org/wiki/Longest_path_problem#Acyclic_graphs_and_critical_paths.  For unweighted DAGs, this sounds like essentially the same thing as your topological sort.

Hamiltonian Path is NP-hard on digraphs with cycles, and on undirected graphs.