# Partitioning bag of sets such that each set in a group has a unique element

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.

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