Question

2. Design a deterministic algorithm to solve the following problem.
input: A directed acyclic graph G = (V, E) stored using adjacency lists.
output: A Hamiltonian path, if such a path exists. Otherwise, return NONE.

Your algorithm must take O(|V| + |E|) time. You must describe your algorithm in plain English (no pseudocode) and you must explain why the running time of your algorithm is O(|V| + |E|). Maximum half a page

Answer 1

To find if there is a Hamiltonian path in a DAG(or directed acyclic graph), we will use the concept of topological sorting. In topological sorting we order the vertices of the graph in such a way that for all the directed edges xy present in the DAG, vertex 'x' comes before vertex 'y' in the ordering. Topological sort in DAG can be computed in O(|V| + |E|) time. Topological sort can be performed easily in O(|V| + |E|) by repeatedly computing indegrees of vertices. After performing the topological sort we just need to check that if there exists an edge between each of the consecutive vertices in the topological order(This can be done in O(|V| + |E|) time by amortized analysis). If it is so, then there exists a hamiltonian path else not.