Given a collection of sets $C= \{ S_1, S_2, \dots, S_n \}$, is there a subset $S'$ of $C$ such that $|S'| - |\bigcup_{S_i \in S'} S_i| \geq k$?
I know that this problem is similar to problems like minimum k-union and maximum coverage. However, they both rely on a limiting factor for the number of sets chosen, which is not necessarily true for my problem.
Build a bipartite graph where on one side, you have the $S_i$ as vertices and on the other side the elements of the $S_i$'s. Link an element $e$ to a set $S_i$ if $e\in S_i$.
$|S'| - |\bigcup_{S_i \in S'} S_i|$ is equal to the deficiency of this graph, and is computable in polynomial time by computing the maximum matching. If $c$ is the size of a maximum matching, then the deficiency is given by $|C|-c$