Suppose I have a bag (or multiset) of sets $S = \{s_1, s_2, \dots, s_n\}$ and $\emptyset\notin S$. I wish to partition $S$ into groups of sets such that within each group each set has at least one element not found in any other set in that group. Formally, the criterion for a group $G = \{g_1, g_2, \dots \} \subseteq S$ is:

$$\forall i: \left(g_i \setminus \bigcup_{j\neq i} g_j\;\neq\;\emptyset\right) $$

The partition $P = \{\{s_1\}, \{s_2\}, \dots\}$ always satisfies this requirement, so there is always a valid solution. But what is the smallest number of groups needed? Is this problem feasible or NP-complete?

Another formulation of this problem is to partition a multiset of integers into groups such that each integer has a bit set in its binary expansion that no other integer in its group has set.

  • $\begingroup$ Basically, if you build only one group containing $S$, it satisfies the constaint, doesn't it ? $\endgroup$ – Optidad Dec 11 '19 at 9:35
  • 1
    $\begingroup$ @Vince Most certainly not. Consider $S = \{\{1, 2\}, \{2, 3\}, \{1, 3\}\}$. $\endgroup$ – orlp Dec 11 '19 at 12:21
  • $\begingroup$ Ok thanks, it's clearer for me. $\endgroup$ – Optidad Dec 11 '19 at 13:18

It is NP-hard. Here is a reduction from a variant of vertex cover:

Given a graph $G$ with $n$ vertices and a positive integer $k$ where $n+k$ is even, determine whether there is a vertex cover with size $k$.

This variant is also NP-complete.

Given an instance graph $G$ with $n$ vertices $v_1,\ldots,v_n$ and $m$ edges $e_1,\ldots,e_m$, as well as an integer $k$, we construct $nm+1$ elements $x_{11},\ldots,x_{1m},\ldots,x_{nm},y$. We define $U=\{x_{11},\ldots,x_{1m},\ldots,x_{nm},y\}$ for convenience. Also,

  • For each vertex $v_i$, we construct a vertex set $S_i=U\backslash\{x_{i1},\ldots,x_{im}\}$.
  • For each edge $e_j=(v_{i_1},v_{i_2})$, we construct an edge set $T_j=U\backslash\{x_{i_11},\ldots,x_{i_1m},x_{i_21},\ldots,x_{i_2m},y\}$.

We ask if $\{S_1,\ldots,S_n,T_1,\ldots,T_m\}$ can be partitioned into $(n+k)/2$ groups such that within each group each set has at least one element not found in any other set in that group.

If there is a vertex cover with size $k$, say without loss of genrality $\{v_1,v_2,\ldots,v_k\}$, then the partition can be $\{S_1,T_{c(1,1)}, T_{c(1,2)},\ldots\}, \ldots, \{S_k,T_{c(k,1)}, T_{c(k,2)},\ldots\}, \{S_{k+1},S_{k+2}\},\ldots,\{S_{n-1},S_n\}$ where $v_i$ covers $e_{c(i,1)}, e_{c(i,2)}, \ldots$

On the other hand, if there is a $(n+k)/2$-partition, we can always adjust it to the form above without increasing the number of groups, thus obtain a vertex cover with size $k$. The adjustment is roughly described as follows:

  • If a group $\mathcal{G}$ contains no vertex set and the number of edge sets it contains is not 2 (i.e., it contains no less than 3 edge sets or only 1 edge set), then the corresponding edges must be incident to a same vertex $v_i$. There are two cases depending on the group $\mathcal{G}'$ containing $S_i$.
    • If $\mathcal{G}'$ does not contain any other vertex set, we merge it with $g$.
    • If $\mathcal{G}'$ contains another vertex set, we move $S_i$ from $\mathcal{G}'$ to $\mathcal{G}$.
  • If a group contains no vertex set and exactly 2 edge sets, we break this group into two groups where each group contains exactly 1 edge set, then we apply the step above for each group.

As a result, this reduction does work and the decision version of your problem is NP-complete.


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.