Finding users covering a set x by x

Question

I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where
$S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$.

Every time I add a new entry to $c$, i.e. adding a new user $u$ with her associated subset of $S^{\prime}$, I need to get the list of other users with whom she covers $S$. However, I don't need to get all possible covers. I only need to get with how many $x$ other users she covers $S$, at most. In other words, I need to find who's complementing each other to cover $S$ 2 by 2, 3 by 3, ... , $x$ by $x$.

Is there an efficient method to do it? Or an efficient data structure? If no, is there any trick I can make to get good results? e.g. encode the elements of $S$ and do some sort of mathematical operations? Is any efficient solution possible at all?

Please let me know if I haven't explained my problem well enough.

Answer 1

Since SET COVER can be reduced to this problem, you can't expect it to have an efficient solution. To reduce SET COVER to your problem, add a dummy user $u$ covering an auxiliary element, add the other users corresponding to the sets in the instance of SET COVER, determine the counts as in your problem, and then you can tell whether there is a set cover of given size.