**Problem 1**:
Does the instance of PCP with pairs (01,12), (0,01), (12,20), and (2,0) have a
solution? Either find one or give a proof that it does not.

**Problem 2**:
The *Chain-Selection Problem* is: given

- A
*budget*m, - A
*target*t, - A
directed graph G that consists of disjoint
*chains*only (a chain is a sequence of nodes n_{1}, n_{2},..., n_{k}, such that the only arcs among these nodes are from n_{i}to n_{i+1}, for i = 1, 2,..., k-1), and - A
*value*v_{i}for each node n_{i},

can we select *m* nodes, whose values sum to at least *t*, subject to the constraint
that if we select a node, then we must select its predecessor, if any, in its chain?

Example: An example of a chain graph has nodes 1, 2,..., 10 and arcs 1→2, 2→3, 3→4, 6→7, 7→8, 8→9, and 9→10. The chains are 1-2-3-4, 5, and 6-7-8-9-10. In this graph, with a budget of 4, we could choose nodes {1, 2, 5, 6}, or {6, 7, 8, 9}, for example, but we could not choose {1, 2, 7, 8}, because it is not permitted to choose 7 without choosing its predecessor 6 in its chain.

Your question: Is the Chain-Selection Problem NP-complete or is it in **P**? Either give a reduction
to show it is NP-complete or give a polytime algorithm to solve it.

Aside: This problem actually surfaced recently as a problem about materialized-view selection in databases. However, we can see it as one of choosing items to purchase in an environment where it doesn't make sense to purchase one item until you have purchased all the previous items on a chain. For instance, one chain might be "a TV" → "cable service" → "high-def decoder box." It doesn't make sense to buy cable service if you have no TV, and it doesn't make sense to get a decoder box unless you have cable service.

A Hint is available.

**Problem 3**:
The *Quadratic Allocation Problem* is: given

- Nonnegative integers
*a*and*b*, - A list of integers i
_{1}, i_{2},..., i_{k}, and - An integer
*limit**l*,

can we select a subset of the integers on the list i_{1}, i_{2},..., i_{k},
such that the sum of ai+bi^{2} over all selected integers i equals the limit *l*?
Note: all integers are assumed represented in binary for this problem.

Is the Quadratic Allocation Problem NP-complete or is it in **P**? Either give a reduction
to show it is NP-complete or give a polytime algorithm to solve it.

Aside: This problem arose during some consulting I was doing, where the integers represented the sizes of different software jobs, and the quadratic term is there because the cost of implementing software goes up faster than linearly with the size of the job.

A Hint is available.