-2
$\begingroup$

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?

$\endgroup$
0
2
$\begingroup$

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.

[1] https://en.wikipedia.org/wiki/Edge_cover [2] https://www.youtube.com/watch?v=mr1FMrwi6Ew&t=2780

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.