Complexity of finding the maximal number of pair-wise disjoint sets

Question

Assume that I have $P$ sets with elements taken from $r$ possible ones. Each set is of size $n$ ($n<r$), where the sets can overlap. I want to determine whether the following two problems are NP-complete or not:

Problem A. Are there $M$ ($1 \le M \le P$) distinct sets within the $P$ sets (i.e., their pair-wise intersection is empty)?

Problem B. Now $k$ ($k<n$) elements can be chosen from each set. Are there $L$ ($1 \le L \le P$) distinct sets of size $k$ each within the $P$ sets? Note that only one set of $k$ elements can be taken from each set of $n$ elements.

Remark: I am mainly interested in the case where $k,n$ are fixed ($n \ge 2, k \ge 2$).

I think that Problem A can be thought as an $n$-uniform $r$-partite hyper-graph matching problem. That is, we have the elements of $r$ as vertices, and each hyper-edge contains a subset of $n$ vertices of the graph.

1. In the $n$-uniform $r$-partite hyper-graph matching problem NP-complete?

2. I think that Problem B is equivalent to finding the number of distinct hyper-edges of cardinality $k$ taken from hyper-edges of cardinality $n$. Is this restricted version (in the sense that each $k$-cardinality set is taken from a pre-chosen set of $n$ elements rather than taken arbitrarily from $r$ elements) of Problem A NP-complete?

Example ($n=3,r=5, P=3$):

$A=\{1,2,3\}$, $B=\{2,3,4\}$, $C=\{3,4,5\}$

If $k=n=3$, there is only $M=1$ one distinct set, which is $A$ or $B$ or $C$, since each of the pairs $(A,B)$, $(A,C)$, $(B,C)$ has non-empty intersection.

If $k=2$, we have $L=2$ distinct sets: one solution is $\{1,2\}$, $\{3,4\}$ (subsets of $A$ and $B$).

Answer 1

This is a special case of the Maximum Set Packing Problem and both problem A and B are NP-Complete. Note that the problem is simply a matching problem if $n=2$ and is also easy if $n=1$. So I'll assume $n \ge 3$.

Instead of asking the question,

Are there $M$ disjoint sets among the $P$ sets?

Let's ask the following question

What is the maximum number of disjoint sets we can obtain from the $P$ sets?

It is clear that if the second question is answerable in polynomial time, then so is the first since all we have to do is compare this maximum value to $M$ and output YES if $M$ is less than or equal to this maximum and NO otherwise.

Also, if the first question is answerable in polynomial time, then the second is too since we can use binary search on $M$ and obtain the answer to the second question and only add a factor of $O(\log{M})$

So we can conclude that both questions are equivalent. i.e. Question 1 is polylomial time solvable if and only if Question 2 is too.

It is also clear that the problems are in NP since we can easily verify that the $M$ sets outputed are disjoint.

So the question now is how do we reduce a known NP-Hard problem to this? To do this we reduce from the maximum set packing problem. I'll simply focus on problem A since problem B can easily be shown to be hard by setting $k=n-1$

Consider an arbitrary instance of the maximum set packing problem $T$. Note that the only difference between problem A and the original maximum set packing problem is that in problem A, the size of the sets have to be equal. Let $t$ be the maximum cardinality among all sets in $T$. If every set in $T$ have the same cardinality, we are done and the set cover problem is exactlly problem A. Now suppose that for some set $S_i \in T$, we have $|S_i| < t$. We simply add $(t-|S_i|)$ elements to $S_i$ which are not elements of any set in $T$. We repeat this process until all sets $S_i \in T$ have the same size. It is clear that adding new elements in this way does not change the size of the maximum number of disjoint sets.

So, if we can solve problem $A$ in polynomial time, we can solve the maximum set packing problem in polynomial time since all we have to do is remove the extra elements that we have added, and doing this doesn't change the size of the maximum number of disjoint sets in $T$.

EDIT - Some Additional information about problem B

Suppose problem B has a polynomial time solution, now consider an arbitrary instance $T$ of problem A with $n$ elements per set. Now we add a dummy element $d$ to each set in $T$. We now ask the following question.

What is the maximum number of disjoint sets we can obtain by taking $n$ elements from each set?

Now we know that among the sets in the maximum, at most one of them can contain the dummy element, hence if the answer we get as the maximum is $M$, then the actual maximum number of sets in instance $T$ (our original problem A) is either $M$ or $(M-1)$, but this gives a constant factor approximation for maximum set packing. And such an approximation is only possible if $P=NP$. So problem B is also hard.