Is the exact cover problem NP-hard when there is a restriction on the size?

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?

Answer 1

Yes, it is still NP-hard. In fact, it remains hard even if you replace $\log_2 n$ with the constant 3. This follows by reduction from 3-dimensional perfect matching.

3-dimensional perfect matching is the following problem:

Input: disjoint sets $X,Y,Z$ such that $|X|=|Y|=|Z|$; a set $T \subseteq X \times Y \times Z$

Question: does there exist a perfect matching? In other words, does there exist $S \subseteq T$ such that $|S|=|X|$ and the union of elements of $S$ is an exact cover for $X \cup Y \cup Z$?

From this statement of the problem, it is clear that 3-dimensional perfect matching is a special case of your problem: take $U=X \cup Y \cup Z$ and $C = \{\{x,y,z\} : (x,y,z) \in T\}$.

---

In contrast, if the size of every set is at most 2, then it can be solved in polynomial time, using algorithms for finding a perfect matching in an undirected graph.