We have:
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.
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.
Please help me how to prove it?, thanks a lot.
First of all this problem is equivalent to the following: In a graph with m nodes, find a set of n nodes that do not neighbor each other on the graph. As it should not be too hard to show that the latter reduces to the former, and the former reduces to the latter.
Then you can take the complement of the above graph $G^c$, and your problem is equivalent to finding if there is a fully connected subgraph with n nodes. If you can solve that, you can solve the maximum clique problem, which is known to be NPC. And huraay, we are done