# Set cover with small subsets [closed]

Has the variant of the Set Cover problem where each set is of size at most $$d$$, for some given $$d$$, been studied? Is it polynomial-time solvable for $$d=2$$ and NP-hard for $$d=3$$ like SAT?

Set cover for $$d=2$$ is the edge cover problem, which is a poly-time problem [1]. For $$d=3$$, it is indeed NP-complete. This can be shown using the same reduction from 3SAT to 3-dimensional matching shown in [2], in which given a 3SAT instance, one can construct a universe $$U=\{1,\dots,N\}$$ and a set $$S$$ of 3-sets such that there is an exact cover of $$U$$ (i.e a set of $$N/3$$ sets of $$S$$ that cover $$U$$) iff the $$SAT$$ instance is satisfiable.