# Is this problem NP-complete?

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?

• It's not NP-complete because it is not a decision problem. It might be NP-hard. Your first step is to formulate the corresponding decision problem, then try to find a reduction. What's the definition of the "minimal k union problem"? What have you tried? What possible reduction partners have you tried (i.e., what problems have you tried reducing from)? – D.W. Dec 27 '17 at 20:59

## 1 Answer

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.