Final answer:
A Hamiltonian path in a directed acyclic graph is a path that visits every vertex exactly once. Determining if a directed acyclic graph has a Hamiltonian path is a polynomial-time solvable problem.
Step-by-step explanation:
A Hamiltonian path in a directed acyclic graph is a path that visits every vertex exactly once. Determining if a directed acyclic graph has a Hamiltonian path is a polynomial-time solvable problem.
To determine if a directed acyclic graph has a Hamiltonian path, we can use a topological sort algorithm. First, we perform a topological sort on the graph to obtain a topological ordering of the vertices. Then, we check if there is an edge between adjacent vertices in the topological ordering. If there is, it means there is a Hamiltonian path in the graph.
Since the time complexity of the topological sort algorithm is O(V + E), where V is the number of vertices and E is the number of edges, we can solve the Hamiltonian path problem for directed acyclic graphs in polynomial time. Therefore, the correct option is C. Polynomial-time solvable.