A subset grouping problem

Question

I'm trying to reduce the following problem to a more well-known formulation.

I have a bunch of subsets $\{S_i \}_{i \in I}$ of some finite set.

I would like to put them into (disjoint) groups $\{ G_j \}_{j \in J}$ such that $\max_{j \in J} \left| \bigcup \{S \in G_j\} \right|$ is as small as possible. The number of groups $|J|$ is a fixed constant $k$.

An example: $k = 2$, $S_1 = \{a, b\}$, $S_2 = \{b, c\}$.

If $G_1 = \{S_1\}$ and $G_2 = \{S_2\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1|, |S_2|\} = 2$$

If instead $G_1 = \{S_1, S_2\}$ and $G_2 = \{\}$, then

$$ \max_{j \in J} \left| \bigcup \{S \in G_j\} \right| = \max\{|S_1 \cup S_2|, |\{\}|\} = 3$$

so the latter grouping is worse than the former.

Answer 1

I don't know of a way to reduce your problem to a more well known formulation, but I can prove that your problem is NP-hard:

In particular, consider the decision version in which we ask whether it is possible to make $\max_{j\in J}|\bigcup\{S \in G_j\}|$ less than or equal to some threshold $T$.

I prove below by reduction from clique that this decision problem with $k = 2$ is NP-hard.

---

First the reduction:

---

Suppose we are given a graph $G = (V, E)$ with $n$ vertices and $m$ edges and a value $c$. We wish to know whether $G$ has a clique of size $c$. We use $G$ and $c$ to construct an instance of your problem.

Define $t_1 = n + m - {c \choose 2}$ and define $t_2 = {c \choose 2} + c$. Then we set the threshold value $T$ to equal $2t_1 + 2t_2$.

We set the universe of elements $U = \bigcup_{i \in I} S_i$ to equal $$\{a_1, a_2, \ldots, a_{T-t_1}\} \cup \{b_1, b_2, \ldots, b_{T-t_2}\} \cup V \cup E$$.

We create exactly $m + 2$ subsets $S_i$:

• We define $S_1$ to be $\{a_1, a_2, \ldots, a_{T-t_1}\} \cup V$.
• We define $S_2$ to be $\{b_1, b_2, \ldots, b_{T-t_2}\}$
• If $E = \{e_1, e_2, \ldots, e_m\}$, then for $i = 1, \ldots, m$ we define $S_{i+2}$ to be $\{e_i, x, y\}$, where $x$ and $y$ are the two endpoints of $e_i$

---

Now I'll prove correctness:

---

There are only two $G_j$s. Note that $S_1$ and $S_2$ cannot be in the same $G_j$ because $|S_1 \cup S_2| = 2T -t_1-t_2+n = T + t_1 + t_2 + n > T$. As a result, the two $G_j$s will contain one of $S_1, S_2$ each. Without loss of generality, suppose $G_1$ contains $S_1$ and $G_2$ contains $S_2$.

Let $E_1$ be the set of edges $e_i$ such that $S_{i+2}$ is in $G_1$ and similarly let $E_2$ be the set of edges $e_i$ such that $S_{i+2}$ is in $G_2$.

Then consider the value $|\bigcup\{S \in G_1\}|$. $G_1$ consists of $S_1$ together with the $S_{i+2}$s for those $i$ for which $e_i \in E_1$. Each $S_{i+2}$ has exactly three elements: two vertices and one edge. But $S_1$ already contains all of the vertices. In other words, we see that the set $\bigcup\{S \in G_1\}$ is equal to $\{a_1, a_2, \ldots, a_{T-t_1}\} \cup V \cup E_1$. Then the size of this set is $(T - t_1) + n + |E_1| = T - (n + m - {c \choose 2}) + n |E_1| = T - (m - {c \choose 2}) + |E_1|$.

Next consider the value $|\bigcup\{S \in G_2\}|$. $G_2$ consists of $S_2$ together with the $S_{i+2}$s for those $i$ for which $e_i \in E_2$. Define $V_2$ to be the set of endpoints of edges in $E_2$. Then the set $\bigcup\{S \in G_2\}$ is equal to $\{b_1, b_2, \ldots, b_{T-t_2}\} \cup E_2 \cup V_2$. The size of this set is $(T -t_2) + |E_2| + |V_2| = (T - {c \choose 2} - c) + |E_2| + |V_2|$.

A partition of edges into $E_1$ and $E_2$ solves this problem if and only if both $T - (m - {c \choose 2}) + |E_1|$ and $(T - {c \choose 2} - c) + |E_2| + |V_2|$ are at most $T$. But $$T - (m - {c \choose 2}) + |E_1| \le T$$ is equivalent to $|E_1| \le (m - {c \choose 2})$, which in turn is equivalent to $|E_2| \ge {c \choose 2}$. Furthermore, $$(T - {c \choose 2} - c) + |E_2| + |V_2| \le T$$ is equivalent to $|E_2| + |V_2| \le c + {c \choose 2}$.

In other words, this problem is solvable if and only if we can choose at least ${c \choose 2}$ edges such that the number of chosen edges plus the total number of vertices incident on those edges is at most $c + {c \choose 2}$. It is possible to choose at least ${c \choose 2}$ edges satisfying this constraint if and only if it is possible to choose exactly ${c \choose 2}$ edges satisfying this constraint (since choosing extra edges can only make it harder to satisfy the constraint). Thus, this problem is solvable if and only if we can choose exactly ${c \choose 2}$ edges such that the number of chosen edges plus the total number of vertices incident on those edges is $c + {c \choose 2}$. In other words, this problem is solvable if and only if we can choose exactly ${c \choose 2}$ edges such that the total number of vertices incident on those edges is at most $c$. This is equivalent to saying that the graph $G$ must have a clique of size $c$. Thus the given reduction is answer preserving.

---

It is also easy to generalize the above reduction to also show the $k > 2$ case hard. For example, to show $k = 3$ hard, we simply add another set $\{c_1, c_2, \ldots, c_T\}$. Then one of the $G_j$s will be forced to contain this $S_i$ and no other, reducing the rest of the problem to the same situation as above.

Answer 2

The problem is NP-complete already for $k=3$ (and I guess also for $k=2$). We reduce the following problem to it: For an input $r$-regular graph $G$, decide whether $G$ has an equitable $3$-coloring, i.e., one where the size of each color class is the same. (I couldn't find a reference for this, but one can easily reduce the classical $3$-coloring problem to this by adding a few extra vertices and edges.)

The reduction is as follows. For each vertex $v$ of the input graph $G$, define a set $S_v=\{\{u,v\}\mid uv\notin E(G)\}$. For any subset $X$ of the vertices we have

$$|\cup_{\{v\in X\}} S_v|=|X|(n-1-r)-|X_2|$$

where $X_2$ is the set of non-adjacent pairs in $X$. If $|X|\ge n/3$, this is at least

$$\frac{n(n-1-r)}3-\binom{\frac n3}{2}$$

with equality only if $|X|=n/3$ and all pairs in $X$ are non-adjacent. Since in any grouping of the $S_v$ into three groups we have such an $X$, we are done.

Answer 3

Joining the club of NP completeness proofs!

This time with $k = 2$. We reduce from the Minimum Bisection problem. Here input is a graph $G$ on $2n$ vertices and an integer $t$, the task is to determine whether there is a partition of $V(G)$ into two sets $A$ and $B$, each of size $n$, such that no more than $t$ edges go between $A$ and $B$. The problem remains NP-hard on $3$-regular graphs (See T. Bui, S. Chaudhuri, T. Leighton, M. Sipser, Graph bisection algorithms with good average case behavior, Combinatorica 7 (1987) 171–191).

Given a $3$-regular graph $G$ and integer $k$ make an instance of the problem by making a universe U that has $10n$ elements for every vertex in $V(G)$ and one element for every edge in $G$. We make a set for each vertex $v$, the set contains all the $10n$ elements corresponding to $v$, and the $3$ elements corresponding to the edges incident to $v$.

Any grouping into groups where both groups have a union of size at most $10n^2 + 10n$ must put exactly $n$ vertices on each side. Each such balanced grouping corresponds to a bisection $(A, B)$ of $G$, where the size of the union of each group is precisely $10n^2 + 3n/2 + |E(A,B)|$ where $E(A,B)$ is the set of edges with one endpoint in $A$ and the other in $B$. (Each vertex covers 3 edges, each edge is covered twice, but the edges with both endpoints on the same side contribute to the size of the union(s) only once.)