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

<p><strong>CURRENT VERSION</strong></p>

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

<p>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 &lt; 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:</p>

<ul>
<li>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$;</li>
<li>add to the $A_1,...,A_n,B_1,...,B_n$ a (new) shared element $z$;</li>
<li>the sets $A_1 \cup \{z\},...,A_n\cup \{z\},B_1 \cup \{z\},...,B_n \cup \{z\}$ represent the input of your problem;</li>
<li>sets to $2p$ the minimum number of subsets required for the solution of your problem (each one must contain $l$ unique elements).</li>
</ul>

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

<ul>
<li><p>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);</p></li>
<li><p>or $q &gt; 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 &gt; p$) that don't include it, so those $p$ subsets $A'_i \subseteq A_i$ represent a valid solution for the original MSP problem;</p></li>
<li><p>or $q &gt; 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.</p></li>
</ul>

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

<p><strong>PREVIOUS VERSION</strong></p>

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

<p><strong>Input</strong>: an integer $q \geq 0$ and a collection $D$ of finite sets, each set contains $k$ elements; an integer $0 &lt; l &lt; k$<br>
<strong>Output</strong>: a set packing of $q$ or more sets, i.e. a collection of <em>partially overlapping</em> sets $D' \subseteq D$ with $|D'| &gt;= 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)</p>

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

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

<p><strong>Reduction</strong>: 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$</p>

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

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

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

CC BY-SA 3.0
2014-07-18T16:00:53.657Z
@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
CC BY-SA 3.0
2014-07-18T16:14:38.687Z
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
CC BY-SA 3.0
2014-07-18T16:35:21.643Z
You're right! I'll think about the $l=2$ case!
Marzio De Biasi
CC BY-SA 3.0
2014-07-19T19:02:24.883Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/15849/discussion-between-marzio-de-biasi-and-mjk).
Marzio De Biasi
CC BY-SA 3.0
2014-07-19T21:50:57.163Z
@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
CC BY-SA 3.0
2014-07-18T10:11:52.490Z
2014-07-20T15:08:20.497Z
2014-07-20T15:08:20.497Z
Marzio De Biasi
<p>(Edited)</p>

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

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

<p>Let us now consider a modified version of the $k$-set packing, which we will call <strong>Problem A</strong>. 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&lt;k$?</p>

<p>Formally:</p>

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

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

<p>Note that for $l=1$ (for any $k$ such that $l \le k$), we can transform our problem to the <strong>maximum bipartite matching problem</strong>, 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 &lt; l &lt; k$.</p>

<p>Examples:</p>

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

<np-hardness><packing>
Hardness of an extended maximum set packing problem
MJK
# Hardness of an extended maximum set packing problem

(Asked by: username_0 on 2014-07-17)

(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

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.

**Tags:** np-hardness, packing

---

## 1 answers

### Answer by username_1 on 2014-07-18. Score: 3 | Accepted answer

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.

> **Comments:**
> **username_1**: @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 ?  
> **username_0**: 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.  
> **username_1**: You're right! I'll think about the $l=2$ case!  
> **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/15849/discussion-between-marzio-de-biasi-and-mjk).  
> **username_1**: @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$).  

---

