CPSC 411: Quiz 11
November 13, 2008

Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."


  1. (2 pts) Suppose you know that the Hamiltonian cycle problem (HC) is NP-complete and you need to prove that the vertex cover problem (VC) is NP-complete. You need to show that there is a reduction from one of these problems to the other. Which way should the reduction go: given any HC input, construct a VC input, OR given any VC input, construct a HC input?

  2. (2 pts) Suppose f is a polynomial reduction from the traveling salesman problem (TSP) to the 3SAT problem. So given a TSP input x, f produces a 3SAT input f(x). Which of the following relationships must hold between x and f(x)? Choose one.

  3. (1 pts) True or False: Suppose we know that there is a polynomial reduction from problem P1 to problem P2. If there is a polynomial-time algorithm for P1, then there is a polynomial-time algorithm for P2.