-1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – karmanaut Jul 26 '18 at 16:11
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Well OP says that $U' \subset U$ so it is not a special case per se. $\endgroup$ – karmanaut Jul 26 '18 at 11:01

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.