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

Problem Detail: 

Exact cover by 3-sets is $\sf{NP}$-complete:

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

Gonzalez called this variant RXC3, for "Restricted Exact Cover by Three Sets."

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/12598

 Ask a Question

 Download Related Notes/Documents