EDIT (Aug 1):
I posted a small report with a more detailed proof on my blog; the reduction idea is the same, but the "gadget" used are better explained (you can also directly download the pdf from here)
The problem seems NP-complete and this is a possible reduction from SET COVER.
Suppose you have an universe $A$ of $n$ elements: $A = \{a_1,...,a_n\}$, a collection of $m$ subsets $\mathcal{S} = \{S_1,S_2,...,S_m\}$ (with $S_i \subseteq A$) and an integer $k$. The SET COVER problem asks for a sub-collection $\mathcal{C} \subseteq \mathcal{S}$ of size at most $k$ such that $\bigcup_{S_i \in \mathcal{C}} S_i = A$ (with $|\mathcal{C}| \leq k$).
The reduction to your problem (I call it 3DM-relaxed, 3DMR) can be done in the following way.
The subsets $S_i$ are simulated using one or more elements of the set $X$, the elements of the universe $A$ are simulated using elements of the sets $Y$ and $Z$ ($a_{2j}$ is simulated with an element $y_{a_{2j-1}}$ of $Y$, $a_{2j-1}$ is simulated with an element $z_{a_{2j}}$ of $Z$).
We start with $X = \{ e_1,e_2,...,e_{k} \}$ that will force the $|\mathcal{C}|=k$ constraint.
Then, for every subset $S_i$ we create the triple: $(x^1_{S_i}, y_{S_i}, dum)$, where $dum$ is a new element of $Z$; and add the $k$ triples:
$(e_1,y_{S_i}, dum),(e_2,y_{S_i}, dum),...,(e_{k},y_{S_i}, dum)$
Note that all $dum$ elements are distinct!
In this way at most $k$ of the $x^1_{S_i}$ will be "free" to cover the elements representing the $a_j$: indeed the $(e,\cdot,\cdot)$ triples can include at most $k$ of the $y_{S_i}$, the remaining $m-k$ must be included by the corresponding $(x^1_{S_i},\cdot,\cdot)$ triple.
To link the $x^1_{S_i}$ to the elements $y_{a_{2j}}, z_{a_{2j-1}}$ that correspond to the elements of the universe in $S_i$, we add three bridge triples:
$(x^1_{S_i},y_{B_i},z_{B_i})$,
$(x^2_{S_i},y_{B_i},dum)$,
$(x^3_{S_i},dum,z_{B_i})$
At this point the elements of $A$ can be linked to $x^2_{S_i}$ and $x^3_{S_i}$ (or we can further extend the capacity of $S_i$ adding more bridge triples).
For example adding the triples:
$(x^2_{S_i},y_{a_2},z_{a_1}), (x^3_{S_i},y_{a_4},z_{a_3})$ we simulate the set: $S_i = \{ a_1, a_2, a_3, a_4\}$.
The fundamental point is that if $x^1_{S_i}$ is "used" to cover the element $y_{S_i}$ (blue edges in the figure) then:
- $x^2_{S_i}$ must be used to include element $y_{B_i}$ and cannot be used to include elements $y_{a_2}, z_{a_1}$ (red edges in the figure);
- $x^3_{S_i}$ must be used to include element $z_{B_i}$ and cannot be used to include elements $y_{a_4}, z_{a_3}$ (red edges in the figure).
Some of the $S_i$ included in the cover can have a non-empty intersection; so we must be sure that two distinct $x^p_{S_i}, x^q_{S_j}$ that are linked to the same element $a_i$ (i.e. we have the triples $(x^p_{S_i}, a_i, \cdot), (x^q_{S_j}, a_i, \cdot)$) can be included in the matching. For this purpouse for every $x^p, p > 1$ we add a triple with two dum elements: $(x^p, dum, dum)$ (green edges in the figure below).
Finally we can add as many distinct triples $(x, y, dum_i), (x, dum_j, z)$ as needed to be able to garbage collect all the dum elements $dum_i \in Z$ and the dum elements $dum_j \in Y$ (otherwise the would not be included in the matching) if they are left alone.
Also note that if there are too many $S_i$, the elements $e_i$ can be included in the matching using their $z_{dum}$ element in $Z$ (only the pair $(e_i, z_{dum})$ is picked).
The resulting 3DMR instance has a solution if and only if there is an set cover $\mathcal{C}$ of $A$ of size at most $k$.
In the figure a triple $(x,y,z)$ is represented with two edges $(x,y),(x,z)$ of the same color. As an example, if $x^1_{S_1}$ corresponding to $S_1 = \{a_1,a_2,a_3,a_4\}$, must be used to include $y_{S_1}$ (blue edges), then it cannot be used to include the elements $z_{a_1},y_{a_2},z_{a_3},y_{a_4}$ (red edges).
