2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If the size of every set is $2$, is it the vertex cover problem? $\endgroup$ – Ribz Dec 14 '16 at 15:30
  • $\begingroup$ @Riebuoz: No, that's perfect matching, which is poly-time-solvable. $\endgroup$ – j_random_hacker Dec 14 '16 at 15:48

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.