Discussion 11
1. In the Min-Cost Fast Path problem, we are given a directed graph G=(V,E) along with positive integer times te and positive costs ce on each edge. The goal is to determine if there is a path P from s to t such that the total time on the path is at most T and the total cost is at most C (both T and C are parameters to the problem). Prove that this problem is NP-complete.
2. We saw in lecture that finding a Hamiltonian Cycle in a graph is NP-complete. Show that finding a Hamiltonian Path — a path that visits each vertex exactly once, and isn¡¯t required to return to its starting point — is also NP-complete.
3. Some NP-complete problems are polynomial-time solvable on special types of graphs, such as bipartite graphs. Others are still NP-complete.
Show that the problem of finding a Hamiltonian Cycle in a bipartite graph is still NP-complete.