Algorithm for finding a Hamiltonian Path in a DAG

Question

I am referring to Skienna's Book on Algorithms.

The problem of testing whether a graph G contains a Hamiltonian path is NP-hard, where a Hamiltonian path P is a path that visits each vertex exactly once. There does not have to be an edge in G from the ending vertex to the starting vertex of P , unlike in the Hamiltonian cycle problem.

Given a directed acyclic graph G (DAG), give an O(n + m) time algorithm to test whether or not it contains a Hamiltonian path.

My approach,

I am planning to use DFS and Topological sorting. But I didn't know how to connect the two concepts in solving the problem. How can a topological sort be used to determine the solution.

Any suggestions?

Hiles

Answer 1

You can first topologically sort the DAG (every DAG can be topologically sorted) in O(n+m).

Once this is done, you know that edge go from lower index vertices to higher. This means that there exists a Hamiltonian path if and only if there are edge between consecutive vertices, e.g.

(1,2), (2,3), ..., (n-1,n).

(This is because in a Hamiltonian path you can't "go back" and yet you have to visit all, so the only way is to "not skip")

You can check this condition in O(n).

Thus, the overall complexity is O(m+n).

Flabellum

But you assumed the graph is connected, can't there be a topological sort for a graph that has disconnected parts? – Nonmoral

I do NOT assume that the graph is connected.If the graph is not connected then there is no Hamiltonian and this algorithm will detect it, because at least one of the consecutive vertices won't be connected (or else the graph will be connected). – Flabellum

What about Hamiltonian cycles, euler path and euler cycles in the same time? – Coworker

I am trying to solve this problem, and came up with this solution: 1. Topologically sort the DAG. 2. run DFS from a source component in the DAG. 3. If the largest pre# in the DFS tree is equal to |V|, there exists such a path. Does this make sense? I am still pretty noob to graphs... – Lattermost

Answer 2

I also tried to solve the same problem as op, but by using DFS and counting the vertices that has an out-degree of 0 and an in-degree of 0.

1. a DAG has at least a vertex with in-degree equal to 0.
2. a DAG has at least a vertex with out-degree equal to 0.
3. a Hamiltonian path exists in DAG if and only if there are exactly one vertex with in-degree equal to 0 and one vertex with out-degree equal to 0.

The time complexity should be O(n+m) since DFS is used and other operations are O(1), although it uses additional data structures like arrays for tracking the count of out-degrees and in-degrees of each node, but the space complexity is still O(n) which is the same with the array for tracking the visited vertices.

Vetiver