2 The Hamiltonian path problem In class, we will show the HAM-CYCLE problem is NP complete. Now, we consider a related problem: HAM-PATH. HAM-PATH problem is similar to HAM-CYCLE: it asks for a path of nodes for graph G, such that the path visits each node exactly once. Note the difference is that in HAM-PATH, we do not need to return the starting node. Now show HAM-PATH is NP complete. 3 NP completeness You are given a tree T and k pairs of nodes of T: (v1;1; v1;2); : : : ; (vk;1; vk;2). You want to find the smallest number of edges of T s.t. deleting these chosen edges will disconnect all these k pairs of nodes (i.e. there exists no path between vi;1 and vi;2 after deletion for each i). Now show this problem is NP complete. Hint: consider using vertex cover and construct a tree of very simple shape (like having height of 1)...
