3
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ How do you write the decision version of Minimum k-Union? $\endgroup$ – zdm Aug 15 '18 at 16:08
  • $\begingroup$ @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. $\endgroup$ – Muoi Tran Aug 16 '18 at 3:34
1
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Muoi Tran Aug 16 '18 at 17:11
  • $\begingroup$ What does the union bound achieve? $\endgroup$ – Pål GD Aug 16 '18 at 17:21
  • $\begingroup$ @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. $\endgroup$ – Thinh D. Nguyen Aug 17 '18 at 3:36
  • $\begingroup$ @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. $\endgroup$ – Thinh D. Nguyen Aug 17 '18 at 3:38
  • $\begingroup$ @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. $\endgroup$ – Muoi Tran Aug 17 '18 at 3:42
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Muoi Tran Aug 16 '18 at 3:59
  • $\begingroup$ 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? $\endgroup$ – Muoi Tran Aug 16 '18 at 17:36
  • $\begingroup$ With $k=0$, then the sets are guaranteed to be pairwise disjoint, no? $\endgroup$ – Pål GD Aug 16 '18 at 18:21
  • $\begingroup$ 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$ $\endgroup$ – Muoi Tran Aug 17 '18 at 0:20

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.