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?