1. Graded Problems
1. State True/False. The set of all vertices in a graph is a vertex cover.
True. Every edge has both its incident vertices (thus at least one) in the set of all vertices.
Remark: A remark about polynomial time reductions: Recall from class that we say that A ≤P B
if given a black box that solves B, we can solve A in polynomial time. A special case of
polynomial time reductions (called as a Karp reduction) is when the black box to solve B is used
just once as shown below (when A and B are both decision problems).
Solve-A(Instance-A){
Instance-B = f(Instance-A);
return (Solve-B(Instance-B));
}
Here Solve-B is the black box that solves B and f is a polynomial time algorithm. To describe a
Karp reduction, we need to describe what f does, that is to which instance of B a given instance
of A gets mapped to. To prove that the reduction is correct, we need to show that Instance-A is
an \yes” (or 1) instance of A if and only if instance-B is an \yes” (or 1) instance of B. In this
homework all our reductions are Karp reductions.
2. State True/False. If A ≤p B and A ∈NP-complete, then B ∈ NP-complete.
False.
If A ≤p B and A ∈ NP-complete, then B is not necessarily in NP-complete (since B need not be
in NP).
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).
We claim that Vertex-Cover ≤p Hitting-Set.
Given an instance (G = (V, E), k’) of the Vertex-Cover problem, we map it to an instance of the
Hitting-Set problem as described below. Let E = {e1, e2, …, e|E|}.Set A =V, B1 = e1 , B2 = e2 , Bm
= em and k = k’.
Remark 1: We have implicitly set n = |V| and m = |E|.
Remark 2: An edge can be considered as a set of two vertices, thus Bi are subsets of A. The
mapping is clearly polynomial time computable.
All that remains to prove is that the mapping preserves membership. That is, G has a vertex
cover of size k’ if and only if the hitting set instance it gets mapped to has a hitting set of size k.
(Note k=k’)
This follows from the fact that C ⊆ V is a vertex cover of G is and only if C is a hitting set of the
corresponding instance. (A =V, B1 = e1 , B2 = e2 , Bm = em and k = k’) (Check for your self that
this is the case!).
From class, we know that Independent-Set ≤p Vertex-Cover. From the transitivity of polynomial
time reductions, it thus follows that Independent-Set ≤p Hitting-Set.
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.
Solution: