[Solved]: Name of an Exact Cover by 3 sets variant

Instance: Given a finite set $X = { x_1,x_2,…,x_{3n}}$ of $3n$ elements and a collection $C = { ( x_{i_1}, x_{i_2}, x_{i_3}) } $ of $m$ 3-elements subsets of $X$;
Question: Find a subcollection $C’$ of $C$ such that every element in $X$ is contained in exactly one member of $C’$.

The problem remains NPC even if we add the following condition:

• every element of $X$ appears exactly in three subsets of $C$

Has this variant an “official” name?

Asked By : Vor

Answered By : rphv

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12598  Ask a Question  Download Related Notes/Documents