Convering by triples
Data: A set Y of cardinality 3n and a family C = ($C_{1},...C_{m}$) of triples of elements of Y: for all i, $C_{i}$ $\subset Y$ and |$C_{i}$| = 3.
We admit that COVERING BY TRIPLES is NP-complete.
Problem: Is there a subset $C^{'}$ of C which forms a partition of Y: i.e. such that the element of $C^{'}$ are pairwise distinct and the union of $C^{'}$ is Y?
Prove that the problem is in NP-complete.
1) Let G = (X,E) be a graph, S a subset of X and an interger k, we construct the following instance of COVERING BY TRIPLES by considering as a set Y = $S_{1}$ $\cup$ $S_{2}$ $\cup$ $S_{3}$, where the $S_{i}$ are some disjoint copies of S as family of triples C, the triples (x,y,z) of $S_{1}$ $\times$ $S_{2}$ $\times$ $S_{3}$ such that there exists in G a tree of size at most [3k/|Y|] containning the vertices of G which correspond to x, y and z.
2) Let be given a subet Y of size 3n and a family C of triples of Y. We construct an instance with X = {$x_{0}$} $\cup$ C $\cup$ Y as a set of vertices, E = {$x_{0},c$ $\in C$} $\cup$ {(c,y)| c $\in$ C, y $\in$ Y} as a set of edges and S = {$x_{0}$} $\cup$ Y as the set of vertices to be connected and the maximal size of the network must be k = 4n.
Please help me why one of the two constructions that are proposed might be useful, while the other clearly cannot be of any help?, thanks a lot.