# Largest number of sets $k$ among given $m$ sets that give union size lower than a given bound

Given $m$ sets $S_1, S_2, \dots, S_m$ and a bound $b$, find as many sets as possible among $m$ sets, says $S_{i_i}, S_{i_2}, \dots, S_{i_k}$ such that

$$\big| S_{i_i} \cup S_{i_2} \cup \cdots \cup S_{i_k} \big| < b$$ I came across the problem above in computer science research. Since my mathematics background is so-so, I would really appreciate any hints.

• "largest $k$ sets" is ambiguous, please edit to make it clearer. Also, is it an algorithm you are asking for? – Brendan McKay Aug 6 '18 at 6:57
• @BrendanMcKay I have updated the question, hope it is clearer now. I'm looking for an algorithm to find these $k$ sets. Or better, a proof saying this is NP-hard since this problem looks pretty familiar to a set cover problem. Regards, – Tran Muoi Aug 6 '18 at 8:26