1 NP completeness
Do problem 10 part (a) on page 508 of the textbook.
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)...
4 NP completeness
Do problem 4 on page 506 of your textbook. The part (c) needs something that is in the textbook but we did not cover it in class. So you are not required to solve part (c).
