6
$\begingroup$

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.

$\endgroup$
  • $\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
2
$\begingroup$

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\})\cup\{x_{i_1j},x_{i_2j}\}$.

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$ (if $v_i$ and $v_{i'}$ both cover an edge $e_j$, we arbitrarily allocate $T_j$ to one of the groups containing $v_i$ and $v_{i'}$.)

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 at most $k$. First, we observe that

  1. If a group contains at least two vertex sets, then it cannot contain any other set. We call such group a vertex group.
  2. If a group contains exactly one vertex set $S_i$, we call it a mix group. Moreover, if this group contains at least two edge sets, then the edges corresponding to the edge sets in this group must all be incident to the vertex $v_i$. (If a group contains exactly one vertex set $S_i$ and one edge set $T_j$, and the edge $e_j$ is not incident to the vertex $v_i$, we call such group a bad group.)
  3. If a group contains no vertex set, then there exist at most two vertices such that each edge corresponding to an edge set in this group must be incident to one of the two vertices. We call such group an edge group.

The adjustment is roughly described as follows:

  1. We arbitrarily choose two bad groups $\{S_i,T_j\},\{S_{i'},T_{j'}\}$ and regroup them as $\{S_i,S_{i'}\},\{T_j,T_{j'}\}$. We repeat this process until there are at most one bad group.

  2. If there is still a bad group $\{S_i,T_j\}$, suppose $e_j$ is incident to $v_{i'}$, then consider the group containing $S_{i'}$. There are two cases:

    1. This group is a vertex group, say $\{S_{i'}, S_{i''}\}$. Then we regroup these sets to $\{S_{i'},T_j\}$, $\{S_i,S_{i''}\}$.
    2. This group is a mix group. Then we simply move $T_j$ to this group.

After the adjustment above, there is no bad group any more.

  1. For each group containing no vertex set, due to Observation 3, there are two vertices $v_i,v_{i'}$ such that each edge corresponding to an edge set in this group is incident to at least one of $v_i,v_{i'}$. For convenience, we denote respectively by $\mathcal{T}_i$ and $\mathcal{T}_{i'}$ the edge sets with corresponding edges incident to $v_i$ and $v_i'$ (one edge $e_j$ may be incident to both $v_i$ and $v_i'$, we arbitrarily allocate $T_j$ to one of $\mathcal{T}_i$ and $\mathcal{T}_{i'}$). Consider the group(s) containing $S_i$ and $S_{i'}$. There are four cases.

    1. $S_i$ and $S_{i'}$ belong to the same group, then we regroup these sets to $\{S_i,\mathcal{T}_i\},\{S_{i'},\mathcal{T}_{i'}\}$.
    2. The two groups are both vertex groups, say $\{S_i,S_{i''}\},\{S_{i'},S_{i'''}\}$. We regroup these sets to $\{S_i,\mathcal{T}_i\},\{S_{i'},\mathcal{T}_{i'}\},\{S_{i''},S_{i'''}\}$.
    3. The two groups are both mix groups, we then simply move $\mathcal{T}_i$ to the group containing $S_i$, and $\mathcal{T}_{i'}$ to the group containing $S_{i'}$.
    4. One is a mix group (say the group containing $S_i$) and the other is a vertex group (say $\{S_{i'},S_{i''}\}$). We then move $\mathcal{T}_i$ to the group containing $S_i$ and regroup remaining sets to $\{S_{i'},\mathcal{T}_{i'}\},\{S_{i''}\}$.

After these adjustments, there are only vertex groups and "good" mix groups. The vertices corresponding to the vertex sets in these "good" mix groups form a vertex cover.

As a result, the decision version of your problem is NP-complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think there is a problem with the "VC solution $\implies$ solution to OP's problem" direction. Consider the VC instance consisting of a 2-edge path $v_1v_2v_3$, and $k=1$. Clearly choosing just $v_2$ suffices. The constructed solution of the OP's problem is $\{\{S_2, T_{12}, T_{23}\}\}$, but its sole subset doesn't satisfy the uniqueness requirement for $T_{12}$, since $T_{12} \subset S_2$ (and likewise for $T_{23}$). $\endgroup$ – j_random_hacker Sep 8 at 0:22
  • $\begingroup$ @j_random_hacker I have changed the definition of edge set, as well as related arguments. Hope it is correct now. $\endgroup$ – xskxzr Sep 9 at 8:42
  • $\begingroup$ Thanks, that fixes that issue. However it seems that another problem remains: In my example instance, $S_2 \subseteq T_{12} \cup T_{23}$ (originally and after the change to the definition of $T_j$), i.e., $S_2$ does not have any element unique to its group. Separately, it seems that if two adjacent vertices $u$ and $v$ are included in the cover, then the set $T_{uv}$ will be included twice, once in $u$'s group and once in $v$'s -- though I think this can be resolved (at least for this direction) just by arbitrarily choosing one of the two copies to keep. $\endgroup$ – j_random_hacker Sep 10 at 19:33
  • $\begingroup$ @j_random_hacker $y\in S_2$ but $y\notin T_{12}\cup T_{23}$ $\endgroup$ – xskxzr Sep 11 at 0:52
  • $\begingroup$ Sorry, so it is. Thanks! $\endgroup$ – j_random_hacker Sep 11 at 22:42

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.