# Is this problem NP-hard? Maximizing selected sets so that their union is less than k?

There is an NP-hard problem called Minimum k-Union where we are given a set system with $$n$$ sets and are asked to select $$k$$ sets in order to minimize the size of their union.

I'm currently interested in a very similar problem, but don't know how to convert one to another:

Given a set system with $$n$$ sets and a bound $$k$$. Select as many sets as possible while their union is at most $$k$$.

Is this problem NP-hard? Any hint is welcome!

Updated 2020: I found a paper called "Unbalanced Graph Cuts" by Hayrapetyan et al. [ESA'05] which describes the Minimum-size bounded-capacity cut (MinSBCC) problem which is very similar to what I looked for.

• How do you write the decision version of Minimum k-Union? – zdm Aug 15 '18 at 16:08
• @zdm I honestly don't know. My best shot would be "Given a set system and a bound $k$. The question is whether or not there exists a subset of sets that cover $k$ or less". But it is different from what I want, i.e., maximizing the number of selected sets. – Muoi Tran Aug 16 '18 at 3:34

Very easy. Clique problem reduces to yours.

Each set is the 2-element edges $\{u,v\}$ of $G$.

A $k$-clique has as many edges as possible while only involves $k$ vertices. So, $K={k \choose 2}$.

• Much appreciate. I guess we are close to the answer. However, can you elaborate how do you present a set as an edge while each set may contain more than 2 elements (i.e., 2 vertices)? Also, just to confirm, $K$ means maximal clique? – Muoi Tran Aug 16 '18 at 17:11
• What does the union bound achieve? – Pål GD Aug 16 '18 at 17:21
• @Pal GD: If the given Clique instance is a Yes instance, then there are ${k \choose 2} = K$ sets (i.e. edges) which union has $k$ vertices. – Thinh D. Nguyen Aug 17 '18 at 3:36
• @Tran Muoi: You are going in the opposite direction. We are reducing from Clique problem to your problem. So, we are given a graph and being asked for if there exists a $k$-clique. We reduce it to your problem by turning each edge into a 2-element set. – Thinh D. Nguyen Aug 17 '18 at 3:38
• @ThinhD.Nguyen I see. But then isn't that the Clique cannot cover all cases of my problem but only instances where sets are all 2-element set? I'm super new to this field so really appreciate your patience if you can explain in more details. – Muoi Tran Aug 17 '18 at 3:42

Yes, it is NP-hard, and we will show that by reducing from $2$-independent set.

Problem: $2$-independent set
Input: A graph $G = (V,E)$ and an integer $\ell \leq |V|$
Definition: Is there a set of at least $\ell$ vertices $S \subseteq V$ such that for each pair of vertices $u,v \in S$, the distance $\text{dist}_G(u, v) > 2$?

The reduction is as follows:

For an input graph $G = (V, E)$, and input $\ell$, we create an instance of your problem where the set family is $\mathcal F = \{N_G[v] \mid v \in V\}$, and we set $k=0$.

Now, a solution to your problem is a set of sets $\mathcal S \subseteq \mathcal F$ with an empty pairwise intersection. For each $F \in \mathcal S$, pick out a vertex $v$ in $V$ such that $N_G[v] = F$. This vertex set is a $2$-independent set. The original problem, $G, \ell$ is a yes instance if and only if $|\mathcal S| \geq \ell$.

• Hi @pål-gd, really appreciate your comments. However, I'm new to this theory field and the hints are not very straightforward to me, unfortunately. For example, isn't that in the 2-independent set problem, $k$ is the lower bound? Is that why you put $k=0$? Please enlighten me how to convert the problem to an independent set problem. – Muoi Tran Aug 16 '18 at 3:59
• The explanation is much clearer now, thanks! However, the constraint in my problem is the union is at most $k$, not at least. Do I understand correctly that you just solved another problem? – Muoi Tran Aug 16 '18 at 17:36
• With $k=0$, then the sets are guaranteed to be pairwise disjoint, no? – Pål GD Aug 16 '18 at 18:21
• Ah I get you now. Unfortunately, I converted a cs research problem to this, and $k$ cannot be set to 0. In fact, $k$ is given and ranged from $50-200$ – Muoi Tran Aug 17 '18 at 0:20