# Hardness of an extended maximum set packing problem

(Edited)

The maximum set packing problem when the sets are all of equal size, say $k$, is known to be NP-hard for $k \ge 3$.

The requirement in this problem is that the sets in the solution will be pair-wise disjoint. In other words, one have to find as many as possible sets taken from the sets in the problem (each containing $k$ elements) such that no two sets share one element or more.

Let us now consider a modified version of the $k$-set packing, which we will call Problem A. Instead of finding the maximum number of pair-wise disjoint sets, we have to find the maximum number of subsets of the original sets, such that each subset contains at least $l$ elements not shared by any other subset. For $l=k$, we get the maximum $k$-set packing. Is Problem A NP-hard for $l<k$?

Formally:

Input: A collection $A_1,A_2,...,A_n$ of sets of size $k$ each and an integer $l$, $1 \le l \le k$.

Output: The maximum number of subsets $A'_i \subseteq A_i$ such that $\left| {A{'_i}} \right| \ge l$ and $\left| {A{'_i} \cap A{'_j}} \right| = \emptyset$.

Note that for $l=1$ (for any $k$ such that $l \le k$), we can transform our problem to the maximum bipartite matching problem, so in this case Problem A is solvable in polynomial time. Thus, I ask about the NP-hardness of Problem A in the case $1 < l < k$.

Examples:

1. ${A_1} = \left\{ {1,2,3} \right\}, {A_2} = \left\{ {1,2,3} \right\}$ ($k=3$) and $l=1$. Then $A'_1={1}, A'_2={2}$ is a valid solution. This can be achieved by considering $A_i$ as one group of nodes in a bipartite graph, and the elements as the other group, and then looking for maximum matching. Note that for $l=2, l=3$ only one set can be obtained as a solution.

2. ${A_1} = \left\{ {1,2,3} \right\},{A_2} = \left\{ {2,4,5} \right\},{A_3} = \left\{ {3,4,5} \right\}$ (again, $k=3$). For $l=1$, one possible solution is $A{'_1} = \left\{ 1 \right\},A{'_2} = \left\{ 2 \right\},A{'_3} = \left\{ 3 \right\}$. For $l=2$, only $2$ sets can be chosen: $A'{'_1} = \left\{ {1,2} \right\},A'{'_2} = \left\{ {4,5} \right\}$. For $l=3$, one of the original sets can serve as a valid solution. That is, for $l=1$ we get a solution of cardinality (number of sets) $3$, for $l=2$ the cardinality is $2$ and for $l=3$ the cardinality is 1.

The previous reduction doesn't work with the current reformulation of your problem (19 July 2014); however I leave it below, because it is correct for that particular maximum k-set packing problem variant (which is defined in the reduction). Here it is a fix for the current version:

CURRENT VERSION

Again your problem is NP-hard for $l \geq 3$. NOTE that $l$ should not be part of the input otherwise it is simply a generalization of the MAXIMUM $k$-SET PACKING problem (MSP): given an instance of MSP, feed it to your algorithm setting $l = k$; so the NP-hardness proof is immediate.

If $l,k$ are not part of the input, I give you the idea of the reduction for the case $l = k-1$, but it can be easily extended to arbitrary $3 \leq l < k$. Given an instance of MAXIMUM $l$-SET PACKING PROBLEM (MSP), i.e. a collection of sets $A_1, A_2, ..., A_n$ and an integer $p$ that represents the minimum number of sets required for the solution, build an instance of your problem in the following way:

• if $A = \{x_1,...,x_m\} = A_1 \cup ... \cup A_n$ are the elements in the $A_i$, "clone" them: $B = \{y_1,...,y_m\}$ using $m$ new elements and build the corresponding $B_i$: $x_j \in A_i \Leftrightarrow y_j \in B_i$;
• add to the $A_1,...,A_n,B_1,...,B_n$ a (new) shared element $z$;
• the sets $A_1 \cup \{z\},...,A_n\cup \{z\},B_1 \cup \{z\},...,B_n \cup \{z\}$ represent the input of your problem;
• sets to $2p$ the minimum number of subsets required for the solution of your problem (each one must contain $l$ unique elements).

Suppose that a solution exists for your problem. Then we can have the following cases:

• exactly $p$ subsets of $A'_i \subseteq A_i \cup \{z\}$ and $p$ subsets $B'_i \subseteq B_i\cup \{z\}$ are included in the solution; but, by construction, the element $z$ can only be contained in one of them - suppose one of the $A_i$ - but in that case the $p$ sets $B'_i$ (that don't contain $z$) also represent a valid solution for the original MSP problem (because each one of them contains $l$ unique elements);

• or $q > p$ subsets $A'_i \subseteq A_i\cup \{z\}$ and $2p - q$ subsets $B'_i \subseteq B_i\cup \{z\}$ are included in the solution; again the element $z$ can be included in only one of the $A'_i$, but nevertheless we have at least $p$ of them (because $q > p$) that don't include it, so those $p$ subsets $A'_i \subseteq A_i$ represent a valid solution for the original MSP problem;

• or $q > p$ subsets $B'_i \subseteq B_i\cup \{z\}$ and $2p - q$ subsets $A'_i \subseteq A_i\cup \{z\}$ are included in the solution; this case is similar to the previous one.

In the opposite direction, if a valid solution to the original MSP exists, it also represent a valid solution to your problem: just pick $A'_i = A_i \subseteq A_i \cup \{z\}, B'_i= B_i \subseteq B_i \cup \{z\}$.

PREVIOUS VERSION

The decision version of your problem MAXIMUM $l$-DISJOINT $k$-SET PACKING PROBLEM is:

Input: an integer $q \geq 0$ and a collection $D$ of finite sets, each set contains $k$ elements; an integer $0 < l < k$
Output: a set packing of $q$ or more sets, i.e. a collection of partially overlapping sets $D' \subseteq D$ with $|D'| >= q$ and foreach $A_i, A_j \in D', | A_i \cap A_j | \leq k - l$ (the last contraint means that two subsets must contain at least $l$ distinct elements)

When $l \geq 3$ the above problem remains NP-hard and this is a reduction from the decision version of MAXIMUM $l$-SET PACKING PROBLEM which is NP-hard because $l \geq 3$ ($k=l$):

Input: an integer $p \geq 0$ and a collection $C$ of finite sets, each set contains $l \geq 3$ elements;
Output: a set packing of $p$ or more sets, i.e. a collection of disjoint sets $C' \subseteq C$ with $|C'| >= p$

Reduction: simply pick $q=p$, and add $k - l$ new shared elements $Y = \{y_1,...,y_{k-l}\}$ to every original set $A_i \in C$; i.e. $D \ni A'_i = A_i \cup Y$

Suppose that $A'_i, A'_j \in D'$ (where a D' is a valid solution to your problem), then by construction they already share $k-l$ elements (the $y_i$s); so they cannot share more elements, otherwise the number of disjoint elements would be less than $l$: $(A'_i \setminus Y) \cap (A'_j \setminus Y) = \emptyset$.

But $A'_i \setminus Y$ contains exactly the elements of the original $A_i \in C$, and $A'_j \setminus Y$ contains exactly the elements of the original $A_j \in C$, so $A_i \cap A_j = \emptyset$ and we can conclude that the solution $D'$ corresponds to a valid solution $C'$ of the original problem.

The opposite direction (if there exists a valid solution $C'$ for the $l$-SET PACKING PROBLEM then there is also a valid solution $D'$ to your problem) is immediate.

• @MJK: yes! I swapped the roles of $C, D$ in the reduction :-S I fixed it changing the name of the collections in the definition of the problems to "follow" the reduction direction: $C \to D$. For what regards the $l=2$ case, I'm still thinking of the case $l=1,k=3$ (which seems NPC using another reduction I'm working on); are you sure that for $l=1$ the problem corresponds to max bipartite matching problem ? – Marzio De Biasi Jul 18 '14 at 16:00
• Consider a bipartite graph $G=(X,Y,E)$. When $l=1, k \ge l$, take the nodes in $X$ as the sets, and the nodes in $Y$ as the elements. Connect each set to its corresponding elements. The maximum matching is exactly the required solution. – MJK Jul 18 '14 at 16:14
• You're right! I'll think about the $l=2$ case! – Marzio De Biasi Jul 18 '14 at 16:35
• – Marzio De Biasi Jul 19 '14 at 19:02
• @MJk: After the discussion in chat, I noticed that $l$ should not be part of the input, otherwise the problem is trivially NP-hard because it is a generalization of the MAXIMUM $k$-SET PACKING problem (given an instance of MAXIMUM $k$-SET PACKING, feed it to your algorithm setting $l = k$). – Marzio De Biasi Jul 19 '14 at 21:50