0
$\begingroup$

(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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @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 ? $\endgroup$ – Marzio De Biasi Jul 18 '14 at 16:00
  • $\begingroup$ 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. $\endgroup$ – MJK Jul 18 '14 at 16:14
  • $\begingroup$ You're right! I'll think about the $l=2$ case! $\endgroup$ – Marzio De Biasi Jul 18 '14 at 16:35
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$ – Marzio De Biasi Jul 19 '14 at 19:02
  • 1
    $\begingroup$ @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$). $\endgroup$ – Marzio De Biasi Jul 19 '14 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.