CODEWITHSUNDEEP
algorithmgraph-algorithmdirected-acyclic-graphshamiltonian-cycle
user2302617
user2302617

Reputation: 399

Algorithm for finding a Hamiltonian Path in a DAG

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?

Upvotes: 36

Views: 39626

Answers (2)

baccano01
baccano01

Reputation: 11

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.

Upvotes: 1

Petar Ivanov
Petar Ivanov

Reputation: 93020

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).

Upvotes: 66

Related Questions