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!

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.

Improve this question
$\endgroup$
2
  • 3
    $\begingroup$ How do you write the decision version of Minimum k-Union? $\endgroup$
    – zdm
    Aug 15, 2018 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, 2018 at 3:34

2 Answers 2

Reset to default
2
$\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}$.

Improve this answer
$\endgroup$
7
  • $\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, 2018 at 17:11
  • $\begingroup$ What does the union bound achieve? $\endgroup$
    – Pål GD
    Aug 16, 2018 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, 2018 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, 2018 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, 2018 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$.

Improve this answer
$\endgroup$
4
  • $\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, 2018 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, 2018 at 17:36
  • $\begingroup$ With $k=0$, then the sets are guaranteed to be pairwise disjoint, no? $\endgroup$
    – Pål GD
    Aug 16, 2018 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, 2018 at 0:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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