0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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)? $\endgroup$ – D.W. Dec 27 '17 at 20:59
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.