Description
1. Problem 1
20 Points Total
CLRS 34.3-2: Show that the ≤P relation is a transitive relation on languages. That is, show
that if L1 ≤P L2 and L2 ≤P L3, then L1 ≤P L3.
2. Problem 2
20 Points Total
Recall the definition of a complete graph Kn is a graph with n vertices such that every vertex
is connected to every other vertex. Recall also that a clique is a complete subset of some graph.
The graph coloring problem consists of assigning a color to each of the vertices of a graph such
that adjacent vertices have different colors and the total number of colors used is minimized. We
define the chromatic number of a graph G to be this minimum number of colors required to color
graph G. Prove that the chromatic number of a graph G is no less than the size of the maximal
clique of G.
3. Problem 3 Note this is a Collaborative Problem
30 Points Total
Suppose you’re helping to organize a summer sports camp, and the following problem comes up.
The camp is supposed to have at least one counselor who’s skilled at each of the n sports covered by the camp (baseball, volleyball, and so on). They have received job applications from m
potential counselors. For each of the n sports, there is some subset of the m applicants qualified
in that sport. The question is “For a given number k < m, is is possible to hire at most k of the
counselors and have at least one counselor qualified in each of the n-sports?” We’ll call this the
Efficient Recruiting Problem. Prove that Efficient Recruiting is NP-complete.
4. Problem 4 Note this is a Collaborative Problem
30 Points Total
We start by defining the Independent Set Problem (IS). Given a graph G = (V, E), we say a set
of nodes S ⊆ V is independent if no two nodes in S are joined by an edge. The Independent
Set Problem, which we denote IS, is the following. Given G, find an independent set that is as
large as possible. Stated as a decision problem, IS answers the question: “Does there exist a set
S ⊆ V such that |S| ≥ k?” Then set k as large as possible. For this problem, you may take as
given that IS is NP-complete.
1
Table 1: Customer Tracking Table
Customer Detergent Beer Diapers Cat Litter
Raj 0 6 0 3
Alanis 2 3 0 0
Chelsea 0 0 0 7
A store trying to analyze the behavior of its customers will often maintain a table A where the
rows of the table correspond to the customers and the columns (or fields) correspond to products
the store sells. The entry A[i, j] specifies the quantity of product j that has been purchased by
customer i. For example, Table 1 shows one such table.
One thing that a store might want to do with this data is the following. Let’s say that a subset
S of the customers is diverse if no two of the customers in S have ever bought the same product
(i.e., for each product, at most one of the customers in S has ever bought it). A diverse set of
customers can be useful, for example, as a target pool for market research.
We can now define the Diverse Subset Problem (DS) as follows: Given an m × n array A as
defined above and a number k ≤ m, is there a subset of at least k customers that is diverse?
Prove that DS is NP-complete.
2
