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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.