Is finding a set cover of size $k$ NP-complete? I know that set cover problem is NP-complete. We are given a universe  $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe and an integer $k$. The set cover problem is to identify a sub-collection of $S$ of size $k$ or less whose union equals the universe?

Now if I remove or less, and ask instead that is there a sub-collection of $S$ of size $k$ whose union equals the universe? Is this still NP-complete?

Here, of course, $k&lt;m$.

My answer is that the problem is still NP-complete. From the initial problem we simply keep the same instance and we find a set cover of size $s\leqslant k$  then the modified problem has a set cover of size $k$ if $s=k$.

Any help?
Yes, it remains NP-complete, even under the restriction that all subsets of a specific size $s$ (which translates to immediately requiring that $k = n / s$.

For example, for $k = n / 3$, 3-dimensional matching can be directly reduced to your problem.