Is Minimum Coverage Problem NP-hard?

Question

Maximum Coverage Problem is NP-hard, it goes like this:

Having $n$ sets $A = \{a_1, a_2, \dots, a_n\}$, choose at most $k$ of them, in such a way, that their union will be as big as possible. $$\max\limits_{B \in 2^\mathit{A}} \bigcup\limits_{b \in B}b\text{ s.t. } \big| B\big| \leq k$$ I have an opposite problem, let me call it Minimum Coverage Problem:

Having $n$ sets $A = \{a_1, a_2, \dots, a_n\}$, choose at least $k$ of them, in such a way, that their union will be as small as possible.

$$\min\limits_{B \in 2^\mathit{A}} \bigcup\limits_{b \in B}b\text{ s.t. } \big| B\big| \geq k$$

Is this problem still NP-hard? If so - why? And if not - how could it be solved?

Answer 1

This is called Minimum k-union problem, and is NP-hard.

Here's source: https://stackoverflow.com/questions/12424155/given-n-sets-of-elements-find-minimal-union-of-m-sets