# Restricted Universe Exact Cover

Apologies for a simple question - I am a beginning graduate student in TCS.

Consider the following $\mathrm{ExactCover}$ problem: Given a collection $\mathcal{S}$ of subsets of a universe set $U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* \subseteq \mathcal{S}$ such that $|\mathcal{S}^*| = K$ and such that each element of $U$ is contained by exactly one subset from $\mathcal{S}^*$.

This problem is known to be NP-Hard and $\mathrm{W}[1]$-complete. The variation of problem I am interested in is the following :

Restricted $\mathrm{ExactCover}$: Given a collection $\mathcal{S'}$ of subsets of a universe set $U$, a subset of universe $U' \subset U$ and an integer $K$, find whether there exists a subcollection $\mathcal{S}^* \subseteq \mathcal{S'}$ such that $|\mathcal{S}^*| = K$ and such that each element of $U'$ is contained by exactly one subset from $\mathcal{S}^*$.

Is anything known about this problem in the literature? I want to show that this problem is still NP-Hard and the proof goes something like this. We will solve the $\mathrm{ExactCover}$ problem by making $|\mathcal{S}|$ number of calls to the Restricted $\mathrm{ExactCover}$ oracle. For each set $S \in \mathcal{S}$, we invoke the oracle with $U' = U \setminus S$, $\mathcal{S'} = \{ T \mid T \in \mathcal{S} \land T \cap U' = T \}$ (consider only sets that can be constructed from $U'$) and $K-1$ as the integer. We accept $\mathrm{ExactCover}$ problem instance if and only if one of the $|\mathcal{S}|$ oracle calls accepts and the there is no intersection between $S$ and $\bigcup_{T \in \mathcal{S^*}} T$ for that oracle.

Is this attempt correct?

• The reduction you've mentioned is a turing reduction (rather than the more standard karp reduction). This is fine for NP-Hardness proofs as such but you need to be aware of this. Second, you can use a simple karp reduction where you make a single oracle call. Just add a new set (say $S''$) with three new elements that don't exist in $U$ and modify $U$ to include these. Now you can make a call to RestrictedExactCover with $U' = U \setminus S''$ and $K-1$. Jul 26 '18 at 16:11

RestrictedExactCover is at least as hard as ExactCover, as ExactCover is a special case of RestrictedExactCover (the special case where $U=U'$). Also, clearly RestrictedExactCover is in NP. It follows that it is NP-complete.
• Well OP says that $U' \subset U$ so it is not a special case per se. Jul 26 '18 at 11:01