# Variant of "Exact Cover by 3-Set "

Exact cover by 3-sets is 𝖭𝖯-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 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'$$.

Now if we impose a restriction on the cardinality (size) of $$C$$, that is, we require $$|𝐶|=(3n/2)-1$$, then is the restricted exact cover by 3 set problem still NP-hard?

• For $|C| = 3n$, the problem is $\mathsf{NP}$-hard: link Dec 1 '21 at 15:15
• Many thanks. Yes, |C|=3n, it is still NP-hard. But how about |C|=(3n/2)-1 ?, is it still NP-hard? Dec 2 '21 at 18:59