# Packing sets to maximize overlap

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.

• An easy statement about the complexity is to reduce from Weighted Set Cover by simply setting $k=|S|$. – chazisop Mar 28 '16 at 6:37
• If I understand your question correctly, you're asking for an algorithm to solve the weighted set cover problem with bounded size, $k$. If you solve the normal weighted set cover problem and find that the minimum cover $C$ requires size $k'$, then don't you simply use $C$ if $k' \leq k$ and declare no solution otherwise? – Lawrence Mar 28 '16 at 11:07
• Thank you for your answers. I tried to come up with a better description of my problem. Hope that the new description is much clearer. – Christos AMS Mar 28 '16 at 13:01
• My understanding is as follows. You have $S = \{S_1, S_2, ... S_m\}$. A configuration is a subset of $S$ with size $\leq k$. The cost of a configuration $C$ is $\sum_{x \in \bigcup C} w(x)$. You want to find a collection of $\leq |U|$ configurations minimizing $\sum_i cost(C_i)$ subject to $\bigcup \bigcup_i C_i = U$. If my understanding is correct, then setting $k=1$ and $w(x)=1$ everywhere means that your cost will be exactly $|U|$ iff the system has an exact cover, doesn't it? It shouldn't get any easier for larger $k$, but that takes an argument that won't fit in the 3 characters left. – Yonatan N Mar 28 '16 at 13:58
• Even after the clarifying remarks, I don't understand the statement of the problem. – Neal Young Mar 29 '16 at 2:39

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