Description
Topic: NP and NP-Completeness
1. (10 Points) Interval Scheduling. Consider the decision version of the problem:
Given a collection of intervals in the timeline, and a bound k, does the collection
contain a subset of non-overlapping intervals of size at least k?
For each statement below, state whether it is “True”, “False”, or “Unknown”, and briefly
justify your answer.
(a) (2 Points) Interval Scheduling is in P.
(b) (2 Points) Interval Scheduling is in NP.
(c) (2 Points) Interval Scheduling is NP-complete.
(d) (2 Points) Interval Scheduling ≤p Vertex Cover.
(e) (2 Points) Independent Set ≤p Interval Scheduling.
2. (35 Points) Vertex Cover on Trees.
For a graph G = (V, E) with |V | = n nodes and |E| = m edges, a vertex cover is defined as a
subset of nodes S ⊂ V s.t. that all edges e are covered (i.e., each edge is touched by at least
one node in S). Let us restrict our attention specifically to graphs that are trees.
(a) (15 Points) Design a greedy algorithm that finds the minimum size vertex cover on a
tree; or argue that such an algorithm does not exist.
(b) (15 Points) Design a dynamic programming algorithm that finds a minimum size vertex
cover on a tree in O(m +n) time. (Note: justify why the running time of your algorithm
is indeed O(m + n).)
(c) (5 Points) Is the polynomial time algorithm in (b) in contradiction with the fact that
the vertex cover is a well-known NP-complete problem? Please explain.
3. (30 Points) The Path Selection Problem.
Consider the path selection problem stated below:
Given a directed graph G = (V, E), a set of paths P1, P2, …Pc, and an integer k > 0,
is it possible to select at least k out of the c paths so that no two of the selected
paths share any nodes?
(a) (20 points) Prove that the path selection problem is NP-complete.
(b) (10 points) Is this a decision or an optimization problem? In which of the six broad
categories of NP-complete problems does this problem belong?
1
4. (25 Points) The Traveling Salesman Problem.
Let’s consider the optimization version of the traveling salesman problem (TSP) : We are
given a graph G(V, E) with n = |V | nodes. Each edge of the graph has an associated distance
dij . The goal is to find a tour, i.e., a cycle that passes through every node exactly once, with
minimum total distance.
(a) (6 Points) State the decision version of the TSP problem. Show that the decision version
of TSP is in NP.
(b) (6 Points) How would you solve the TSP problem using a brute force approach? What
would be the running time of that approach?
(c) (13 Points) Develop a dynamic programming approach that solves this problem and
report the running time of your algorithm.
2