Kleinberg, Jon. Algorithm Design $($p$.506,$ q$.4).$ A system has a set of n processes and a set of m

resources. Each process specifies a set of resources that it requests to use. Each resource might be

requested by many processes; but it can only be used by a single process. 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.