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.
