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.
In the $n$-uniform $r$-partite hyper-graph matching problem NP-complete?
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$).