# Detecting Hamiltonian path in a graph

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

1. Brute force approach. i.e. considering all permutations T(n)=O(n*n!)

2. Backtracking T(n)=O(n!)

3. 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?

• This site works best when you ask only one question per post. If you want to know about correctness, try running it on some examples and you should be able to quickly figure out the answer on your own.
– D.W.
May 17 '18 at 22:14

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.