Question

The exact cover problem with restrictions on the size is:

Input: Given a set $U=\{1,2,\ldots,n\}$ and a collection of $C$ of subsets of $U$.

Question: Is there a subcollection $C^\star$ of $C$ such that

  • The intersection of any two distinct subsets in $C^\star$ is empty;
  • The union of the subsets in $C^\star$ is $U$; and
  • The size of any set $S\in C^\star$ is at most $\log_2 n$, i.e., $|S|\leqslant \log_2 n$ for all $S\in C^\star$.

Is this problem NP-hard?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top