CSCI 338 Homework 10
Problem 1 (10 points). Assuming the only problem you know to be NP-Complete is the
Hamiltonian Cycle problem, show that the Traveling Salesman problem is NP-Complete.
Problem 2 (10 points). Consider the problem of 4SAT: Given a cnf Boolean formula with
exactly four literals per clause, can the literals be assigned values so that the formula
evaluates to true? Using 3SAT, show that 4SAT is in NP − Complete.
Problem 3 (10 points). Assuming the only problem you know to be NP-Complete is the
Clique problem, show that the Vertex Cover problem is NP-Complete.
Problem 4 (5 points). For a complete graph over n vertices, what is the size of the smallest
Vertex Cover, Dominating Set, and largest Independent Set?