1. Graded Problems
1. State True/False. The set of all vertices in a graph is a vertex cover.
2. State True/False. If A ≤p B and A ∈NP-complete, then B ∈ NP-complete.
3. Show that the independent set problem is polynomial time reducible to the Hitting Set problem
(Refer to Kleinberg and Tardos, Chapter 8, Exercise5 for the definition of the Hitting Set problem).
4. A company makes three models of desks, an executive model, an office model and a student
model. Building each desk takes time in the cabinet shop, the finishing shop and the crating shop
as shown in the table below:
How many of each type should they make to maximize profit? Use linear programming to
formulate your solution. Assume that real numbers are acceptable in your solution.
2. Practice Problems
1. Given a graph G = (V, E) and a positive integer k < |V|. The longest-simple-cycle problem is the
problem of determining whether a simple cycle (no repeated vertices) of length k exists in a graph.
Show that this problem is NP-complete.
2. In the Bipartite Directed Hamiltonian Cycle Problem, we are given a bipartite directed graph
G = (V; E) and asked whether there is a simple cycle which visits every node exactly once. Note
that this problem might potentially be easier than Directed Hamiltonian Cycle because it assumes
a bipartite graph. Prove that Bipartite Directed Hamiltonian Cycle is in fact still NP-Complete.
3. Assume that you are given a polynomial time algorithm that decides if a directed graph contains
a Hamiltonian cycle. Describe a polynomial time algorithm that given a directed graph that
contains a Hamiltonian cycle, lists a sequence of vertices (in order) that form a Hamiltonian cycle.