Description
Intractibility
1. Kleinberg, Jon. Algorithm Design (p. 506, q. 4). A system has a set of n processes and a set of m
resources. At any point in time, each process specifies a set of resources that it requests to use. Each
resource might be requested by many processes at once; but it can only be used by a single process at a
time. If a process is allocated all the resources it requests, then it is active; otherwise it is blocked.
Thus we phrase the Resource Reservation Problem as follows: Given a set of processes and resources,
the set of requested resources for each process, and a number k, is it possible to allocate resources to
processes so that at least k processes will be active?
For the following problems, either give a polynomial-time algorithm or prove the problem is NP-complete.
(a) The general Resource Reservation Problem defined above.
Solution:
CS 577 Assignment 11 – Intractability
(b) The special case of the problem when k = 2.
Solution:
(c) The special case of the problem when there are two types of resources–say, people and equipment–
and each process requires at most one resource of each type (In other words, each process requires
one specific person and one specific piece of equipment.)
Solution:
(d) The special case of the problem when each resource is requested by at most two processes.
Solution:
Page 2 of 6
CS 577 Assignment 11 – Intractability
2. Kleinberg, Jon. Algorithm Design (p. 506, q. 7). The 3-Dimensional Matching Problem is an NPcomplete problem defined as follows:
Given disjoint sets X, Y , and Z, each of size n, and given a set T ⊆ X × Y × Z of ordered triples, does
there exist a set of n triples in T that each element of X ∪ Y ∪ Z is contained in exactly one of these
triples?
Since 3-Dimensional Matching is NP-complete, it is natural to expect that the 4-Dimensional Problem
is at least as hard.
Let us define 4-Dimensional Matching as follows. Given sets W, X, Y , and Z, each of size n, and a
collection C of ordered 4-tuples of the form (wi
, xj , yk, zℓ), do there exist n 4-tuples from C such that
each element of W ∪ Y ∪ X ∪ Z appears in exactly one of these 4-tuples?
Prove that 4-Dimensional Matching is NP-complete. Hint: use a reduction from 3-Dimensional Matching.
Solution:
Page 3 of 6
CS 577 Assignment 11 – Intractability
3. Kleinberg, Jon. Algorithm Design (p. 507, q. 6). Consider an instance of the Satisfiability Problem,
specified by clauses C1, …, Cm over a set of Boolean variables x1, …, xn. We say that the instance is
monotone if each term in each clause consists of a nonnegated variable; that is, each term is equal to xi
,
for some i, rather than xi
. Monotone instances of Satisfiability are very easy to solve: They are always
satisfiable, by setting each variable equal to 1.
For example, suppose we have the three clauses
(x1 ∨ x2),(x1 ∨ x3),(x2 ∨ x3).
This is monotone, and the assignment that sets all three variables to 1 satisfies all the clauses. But we
can observe that this is not the only satisfying assignment; we could also have set x1 and x2 to 1, and
x3 to 0. Indeed, for any monotone instance, it is natural to ask how few variables we need to set to 1 in
order to satisfy it.
Given a monotone instance of Satisfiability, together with a number k, the problem of Monotone Satisfiability with Few True Variables asks: Is there a satisfying assignment for the instance in which at most
k variables are set to 1? Prove this problem is NP-complete.
Solution:
Page 4 of 6
CS 577 Assignment 11 – Intractability
4. Kleinberg, Jon. Algorithm Design (p. 509, q. 10). Your friends at WebExodus have recently been doing
some consulting work for companies that maintain large, publicly accessible Web sites and they’ve come
across the following Strategic Advertising Problem.
A company comes to them with the map of a Web site, which we’ll model as a directed graph G = (V, E).
The company also provides a set of t trails typically followed by users of the site; we’ll model these trails
as directed paths P1, P2, …, Pt in the graph G (i.e., each Pi
is a path in G).
The company wants WebExodus to answer the following question for them: Given G, the paths {Pi},
and a number k, is it possible to place advertisements on at most k of the nodes in G, so that each
path Pi
includes at least one node containing an advertisement? We’ll call this the Strategic Advertising
Problem, with input G, {Pi
: i = 1, …, t}, and k. Your friends figure that a good algorithm for this will
make them all rich; unfortunately, things are never quite this simple.
(a) Prove that Strategic Advertising is NP-Complete.
Solution:
Page 5 of 6
CS 577 Assignment 11 – Intractability
(b) Your friends at WebExodus forge ahead and write a pretty fast algorithm S that produces yes/no
answers to arbitrary instances of the Strategic Advertising Problem. You may assume that the
algorithm S is always correct.
Using the algorithm S as a black box, design an algorithm that takes input G, {Pi
: i = 1, …, t},
and k as in part (a), and does one of the following two things:
• Outputs a set of at most k nodes in G so that each path Pi
includes at least one of these nodes.
• Outputs (correctly) that no such set of at most k nodes exists.
Your algorithm should use at most polynomial number of steps, together with at most polynomial
number of calls to the algorithm S.
Solution:
