Detecting Hamiltonian path in a graph

Question

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?

Answer 1

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.