Is this "superset existence" problem NP-complete? The &quot;Superset Existence Problem&quot;:
Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y &lt; |S|$, which is a superset of at least $z$ of those subsets?
To me, this feels like it should be NP-complete (in $|S|$), since it seems intuitively related to covering problems and minimum $k$-union. But I'm not sure where to start with the reduction.
So: is this problem NP-complete?
The problem is NP complete.
It is trivially in $NP$ (a certificate is the collection of the $y$ selected subsets of $S$), and it is $NP$-hard since it is the decision version of the Maximum Coverage Problem.