Description

Answer the questions in the boxes provided on the question sheets. If you run out of room for an answer, add a page to the end of the document.
Name: Wisc id:
Reductions
1. Kleinberg, Jon. Algorithm Design (p. 527, q. 39) The Directed Disjoint Paths Problem is defined as follows: We are given a directed graph G and k pairs of nodes (s1,t1),…,(sk,tk). The problem is to decide whether there exist node-disjoint paths P1,…,Pk so that Pi goes from si to ti.
Show that Directed Disjoint Paths is NP-Complete.
Consider the following situation: You are managing a communications network, modeled by a directed graph G. There are c users who are interested in making use of this network. User i issues a “request” to reserve a specific path Pi in G on which to transmit data.
You are interested in accepting as many path requests as possible, but if you accept both Pi and Pj, the two paths cannot share any nodes.
Thus, the Path Selection Problem asks, given a graph G and a set of requested paths P1,…,Pc (each of which must be a path in G), and given a number k, is it possible to select at least k of the paths such that no two paths selected share any nodes?
Show that Path Selection is also NP-Complete.

Kleinberg, Jon. Algorithm Design (p. 512, q. 14) We’ve seen the Interval Scheduling Problem several times now, in different variations. Here we’ll consider a computationally much harder version we’ll call Multiple Interval Scheduling. As before, you have a processor that is available to run jobs over some period of time.
People submit jobs to run on the processor. The processor can only work on one job at any single point in time. Jobs in this model, however, are more complicated than we’ve seen before. Each job requires a set of intervals of time during which it needs to use the processor. For example, a single job could require the processor from 10am to 11am and again from 2pm to 3pm. If you accept the job, it ties up your processor during those two hours, but you could still accept jobs that need time between 11am and 2pm.
You are given a set of n jobs, each specified by a set of time intervals. For a given number k, is it possible to accept at least k of the jobs so that no two accepted jobs overlap in time?
Show that Multiple Interval Scheduling is NP-Complete.

Kleinberg, Jon. Algorithm Design (p. 519, q. 28) Consider this version of the Independent Set Problem. You are given an undirected graph G and an integer k. We will call a set of nodes I “strongly independent” if, for any two nodes v,u ∈ I, the edge (v,u) is not present in G, and neither is there a path of two edges from u to v. That is, there is no node w such that both (v,w) and (u,w) are present. The Strongly Independent Set problem is to decide whether G has a strongly independent set of size at least k.
Show that the Strongly Independent Set Problem is NP-Complete.