<p>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.</p>

CC BY-SA 4.0
2018-07-26T11:01:12.157Z
Well OP says that $U' \subset U$ so it is not a special case per se.
karmanaut
CC BY-SA 4.0
2018-07-26T06:17:37.373Z
2018-07-26T06:17:37.373Z
D.W.
<p>Apologies for a simple question - I am a beginning graduate student in TCS.</p>

<p>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}^*$. </p>

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

<p>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}^*$.</p>

<p>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. </p>

<p>Is this attempt correct?</p>

CC BY-SA 4.0
2018-07-26T16:11:03.300Z
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$.
karmanaut
<cc.complexity-theory><np-hardness><set-cover>
Restricted Universe Exact Cover
newdude
# Restricted Universe Exact Cover

(Asked by: username_0 on 2018-07-25)

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?

**Tags:** cc.complexity-theory, np-hardness, set-cover
> **Comments:**
> **username_1**: 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$.  

---

## 1 answers

### Answer by username_2 on 2018-07-26. Score: 2

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.

> **Comments:**
> **username_1**: Well OP says that $U' \subset U$ so it is not a special case per se.  

---

