CS 577 Assignment 12  More Intractability solved

Description

Reductions

1. Kleinberg, Jon. Algorithm Design (p. 512, q. 14) We’ve seen the Interval Scheduling Problem several
times now, in dierent 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 specied 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.
CS 577 Assignment 12  More Intractability
2. 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 in G. 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.
Page 2 of 4
CS 577 Assignment 12  More Intractability
3. Kleinberg, Jon. Algorithm Design (p. 527, q. 39) The Directed Disjoint Paths Problem is dened 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.
Page 3 of 4
CS 577 Assignment 12  More Intractability
4. Kleinberg, Jon. Algorithm Design (p. 508, q. 9) The Path Selection Problem may look initially similar to
the problem from the question 3. Pay attention to the dierences between them! 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 specic
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.