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:
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 given 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.

(b) The special case of the problem when k = 2.

(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.)

(d) The special case of the problem when each resource is requested by at most two processes.
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-DimensionaI 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 so that no two have an element in common?
Prove that 4-Dimensional Matching is NP-complete. Hint: use a reduction from 3-Dimensional Matching.

3. Kleinberg, Jon. Algorithm Design (p. 507, q. 6). Consider an instance of the Satisfiability Problem, specified by clauses C1,…,Ck 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.

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.

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 inclujdes 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.