<p>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:</p>

<p>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$.</p>

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

<hr>

<p>First the reduction:</p>

<hr>

<p>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.</p>

<p>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$.</p>

<p>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$$.</p>

<p>We create exactly $m + 2$ subsets $S_i$:</p>

<ul>
<li>We define $S_1$ to be $\{a_1, a_2, \ldots, a_{T-t_1}\} \cup V$.</li>
<li>We define $S_2$ to be $\{b_1, b_2, \ldots, b_{T-t_2}\}$</li>
<li>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$</li>
</ul>

<hr>

<p>Now I'll prove correctness:</p>

<hr>

<p>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 &gt; 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$.</p>

<p>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$.</p>

<p>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|$.</p>

<p>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|$.</p>

<p>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}$.</p>

<p>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.</p>

<hr>

<p>It is also easy to generalize the above reduction to also show the $k &gt; 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.</p>

CC BY-SA 3.0
2017-02-12T22:36:26.457Z
2017-02-12T22:36:26.457Z
Mikhail Rudoy
<p>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.)</p>

<p>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</p>

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

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

<p>$$\frac{n(n-1-r)}3-\binom{\frac n3}{2}$$</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-12T22:02:19.110Z
2017-02-12T22:02:19.110Z
domotorp
<p>Joining the club of NP completeness proofs! </p>

<p>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).</p>

<p>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$.</p>

<p>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.)</p>

CC BY-SA 3.0
2017-02-16T22:58:37.817Z
2017-02-16T22:58:37.817Z
daniello
<p>I'm trying to reduce the following problem to a more well-known formulation.</p>

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

<p>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$.</p>

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

<p>If $G_1 = \{S_1\}$ and $G_2 = \{S_2\}$, then</p>

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

<p>If instead $G_1 = \{S_1, S_2\}$ and $G_2 = \{\}$, then</p>

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

<p>so the latter grouping is worse than the former.</p>

CC BY-SA 3.0
2017-01-29T05:27:35.490Z
This problem is NP-hard. You can reduce 3-partition to it. In particular, given an instance $a_1, ..., a_{3n}$, set $k = n$ and let $S_i$ be a set of $a_i$ elements with the sets $\{S_i\}_{i\in I}$ disjoint. Then the maximum which you are minimizing can be made as small as three times the average of the $a_i$s if and only if the 3-partition instance is a yes instance.
Mikhail Rudoy
CC BY-SA 3.0
2017-02-12T18:39:14.457Z
How about defining a graph where each set as a vertex and edge weights as number of common elements. Then maybe this can be formulated as a cut-flow problem?
padawan
<ds.algorithms>
A subset grouping problem
user357269
# A subset grouping problem

(Asked by: username_0 on 2017-01-29)

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.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: This problem is NP-hard. You can reduce 3-partition to it. In particular, given an instance $a_1, ..., a_{3n}$, set $k = n$ and let $S_i$ be a set of $a_i$ elements with the sets $\{S_i\}_{i\in I}$ disjoint. Then the maximum which you are minimizing can be made as small as three times the average of the $a_i$s if and only if the 3-partition instance is a yes instance.  
> **username_2**: How about defining a graph where each set as a vertex and edge weights as number of common elements. Then maybe this can be formulated as a cut-flow problem?  

---

## 3 answers

### Answer by username_1 on 2017-02-12. Score: 2 | Accepted answer

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 by username_3 on 2017-02-12. Score: 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 by username_4 on 2017-02-16. Score: 2

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.)


---

