## 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