Packing sets to maximize overlap

Question

For a set of sets $A$, let $\cup A := \cup_{S \in A} S$.

Consider the following problem:

Input:

• a list of $m$ weights $w = (w_1, \ldots, w_m)$,
• a list of $n$ distinct subsets $T = (S_1, \ldots, S_n)$ such that $\bigcup_{S\in T} S = [m]$,
• an integer $k$.

Let $P$ be a partition of $T$. We say $P$ is a $k$-good partition when the size of each part is at most $k$: $\forall p \in P \ |p| \leq k$. The cost of $P$ is defined as the sum of weight of items counted once for each part they appear in, i.e. $$cost(P) := \sum_{p\in P} \ \sum_{x\in \cup p} w_x $$

Output: a $k$-good partition of $P$ of $T$ minimizing $cost(P)$.

What is the complexity of this problem?
Is it NP-hard or is there a polynomial-time algorithm?

---

Example:
$m = 7$, $w=(2,2,3,4,1,2,2)$,
$n = 3$, $T=(S_1=\{1,2,3\}, S_2=\{3,4,5\}, S_3=\{5,6,7\})$
$k=2$

In this case, since $k<|T|$, it is obvious that more than one partition is needed. Moreover, $S_1$ and $S_2$ should be packed together in the same configuration because of their heavy overlap ($S_1 \cap S_2$ gives the biggest overlap in our example - we pay 3 less cost units). So the optimal $P$ is $\{S_1, S_2\}, \{S_3\}$ with the total cost 12+5=17.

---

The unweighted version (when the weights of the elements are all 1) is also very interesting to me.

Answer 1

I believe it's NP-hard, by a reduction from min-balanced cut. Given a graph $G=(V,E)$ and integer $\ell$, min-balanced cut asks whether there is a cut that is balanced (has $|V|/2$ vertices on each side), and cuts at most $\ell$ edges. Given $G$ and $\ell$, construct the following instance of your problem. For each vertex $v$, create a set $S_v$ containing the edges incident to $v$. Take $k=|V|/2$. Then the (minimal) $k$-good partitions are partitions of the sets into two equal-size groups, corresponding to the balanced cuts of $G$, and your (unweighted) cost for such a solution equals $|E|$ plus the number of edges cut. Unless I'm mistaken :-).

EDIT: Similarly you can reduce the following problem to yours: given a graph $G=(V,E)$ and integer $\ell$, color the vertices of $G$ so that each color class has at most $k$ vertices, minimizing the number of edges whose two endpoints have the same color. (The reduction: make a set $S_v$ for each vertex $v\in V$, containing the pairs $\{v,w\}$ not in $E$.)