Skip to main content
2 of 2
added 47 characters in body
david
  • 111
  • 3

Your problem definition is somewhat unclear: how can "the answer to this question" not be affirmative, since for every $k$ there will be some maximum number of doors that can be opened with $k$ keys?

If I understand correctly, your problem is: "Given the set of keys necessary to open each door and an integer $k$, what is the maximum number of doors you can open with $k$ keys"? This problem is NP-hard, even when each door requires exactly two keys. Indeed, this special case is the densest $k$-subgraph problem: given a graph, find a set of $k$ vertices with maximum induced number of edges. Each vertex in the graph is a "key" and each edge is a "door" requiring two keys. The best approximation factor known to be achievable in polynomial time is $O(M^{1/4+\epsilon})$, for arbitrarily small $\epsilon > 0$:

https://dl.acm.org/citation.cfm?doid=1806689.1806719

This result does not directly apply to your problem because in your setting, doors may require more than two keys, but it is surely worth looking into.

As an aside, if you were interested instead in finding the largest possible ratio between the number of doors opened and the number of keys necessary to open them, then your problem would become polynomial-time solvable (using techniques similar to those used for the densest subgraph problem, with no restriction on the size of the subgraph). See, e.g., Lemma 4 in the following paper:

https://arxiv.org/pdf/1802.02562.pdf

david
  • 111
  • 3