I'm considering the general resource reservation problem: n processes, m resources. Each process requests a set of resources and each resource can be used by exactly one process. Processes are only active if they have all requested resources.
Instance: A set of processes P, a set of resources R, the set of resource requests for each process, and an int k. Question: Is it possible to allocate resources so that at least k processes are active at the same time?
My initial inclination was that a greedy approach makes sense here. Sort the jobs in increasing order of number of resources requested, then allocate resources to processes until all resources are allocated or all processes have been attempted to be scheduled, as below:
procedure reserve_resources(P, R, k): int jobs_active = 0; Order processes in ascending order of number of resources requested; for each process: if (all of the processes' requested resources are available): allocate resources to that process; jobs_active++; end if; end for; if (jobs_active >= k): return "YES"; else: return "NO"; end if; end procedure;
I've come across an answer for this problem which shows NP-completeness by reducing Independent Set to this resource reservation problem. For the IS instance G = (V, E), it makes the set of resources equal to E, the set of process equal to V, and any edge incident to an vertex is a resource requested by that process. If k processes have disjoint resource requests, then the vertices corresponding to those processes form an independent set.
This reduction makes sense to me and I know that IS is NP. I believe that P != NP, and I certainly don't think I've just proven the opposite while working on homework in my undergrad algorithms class. But I also can't find a counterexample to the algorithm I've presented. My question is, where does this algorithm fail?