3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    May 17, 2018 at 22:14

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I agree and what about the time complexity ? $\endgroup$
    – shiwang
    May 17, 2018 at 19:40
  • $\begingroup$ I think there is an equivalent condition that is easier to check: the topological ordering is unique iff there is never more than 1 sink (vertex with outdegree 0) during the algorithm's execution. $\endgroup$ May 18, 2018 at 7:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.