Complexity of Exact Cover problem if containing a Set Cover means there is an Exact Cover

Question

As stated in the question, I'm interested in a variant of Exact Cover that is currently relevant to my research. Specifically, a variant where you are promised that if there is a Set Cover of size $k$, then there is also an Exact Cover of size $k$ (or less).

More formally, let us define the Exact Cover and Set Cover problems.

Set Cover Given a collection $S$ of of subsets $S_i$ of a set $X$ and a target $k$, does there exist a subcollection $S^{\ast}$ of $S$ of size $k$ or less such that every element in $X$ is contained in $S^{\ast}$?

Exact Cover Does there exist a Set Cover of size $k$ such that every element in $X$ is contained exactly once in $S^{\ast}$?

My modification is

Pure Exact Cover For a given input, categorize the input into one of two cases:

1. There an Exact Cover of size $k$ or less,
2. There is no Set Cover of size $k$.

You are promised that if there is a Set Cover of size $k$, there is also an Exact Cover of size $k$

Is this Pure Exact Cover problem still NP-hard? Or at least, has this problem been examined at all in the research? I can't find anything, but I also have no idea what name it would have.

Answer 1

It's also NP-hard, because Set Cover on sets of constant size is NP-hard, and given an instance of Set Cover with constant-size sets, you can add all the (polynomially many) subsets of the given sets, and you will obtain a new instance which is equivalent (has the same min-size set cover) but also has an exact cover of the same size as the min-size set cover.