Is this problem NP-complete?

Question

Let there be a set of cardinality $n\in \mathbb{N}$. Let there also be $n$ subsets of that set. What is the smallest k such that union of some $n-k$ of those subsets is of cardinality at most $k$? The problem is very similar to minimal $k$ union problem, but is more specific, how can I prove it is NP-complete?

Answer 1

Our problem is NP-complete by a reduction from MAXIMUM BALANCED BICLIQUE PROBLEM (MBBP).

MBBP problem:

Input: A bipartite graph $G(U, V, E)$ and an integer $k$

Output: YES if there exists $A\subseteq U$ and $B\subseteq V$ with $|A|=|B|=k$ and $G[A, B]$ is a biclique, NO otherwise

Given an MBBP instance $G, k$, output the following instance of our problem: $(\bar G, n-k)$ where $\bar G$ is the complement bipartite graph of $G$, namely $\bar G = (U, V, U\times V - E)$.

First, requirement that $|U| = |V|$ in our problem can be easily obtained by adding dummy vertices without harming the hardness of MBBP.

Second, we will show that $(G, k)$ is a YES instance of MBBP iff. $(\bar G, n-k)$ is a YES instance of our problem.

If $(G, k)$ is a YES instance of MBBP, then there exist $A\subseteq U$ and $B\subseteq V$ such that $|A| = k$ and $|B| = k$ and $G[A, B]$ is a biclique. It follows that in $\bar G$ the neighborhood of $A$ is a subset of $V - B$ (all the edges in the biclique are removed). And $|A| = k = n - (n - k)$ and $|V - B| = n - k$. Thus, $(\bar G, n - k)$ is a YES instance of our problem.

Conversely, if $(\bar G, n - k)$ is a YES instance of our problem, then there exist $A\subseteq U$ such that $|\cup_{v\in A}N_{\bar G}(v)| \leq n - k$. By complementing this, we have $|\cap_{v\in A}N_G(v)| \geq k$. So by arbitrarily choose $k$ vertices in $\cap_{v\in A}N_G(v)$ to form $B\subseteq V$. We have shown the existence of a biclique in $G$ satisfying requirement of the original MBBP instance. Hence, $(G, k)$ is a YES instance of MBBP.