<p>Set cover for <span class="math-container">$d=2$</span> is the edge cover problem, which is a poly-time problem [1]. For <span class="math-container">$d=3$</span>, 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 <span class="math-container">$U=\{1,\dots,N\}$</span> and a set <span class="math-container">$S$</span> of 3-sets such that there is an exact cover of <span class="math-container">$U$</span> (i.e a set of <span class="math-container">$N/3$</span> sets of <span class="math-container">$S$</span> that cover <span class="math-container">$U$</span>) iff the <span class="math-container">$SAT$</span> instance is satisfiable.</p>
<p>[1] <a href="https://en.wikipedia.org/wiki/Edge_cover" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Edge_cover</a>
[2] <a href="https://www.youtube.com/watch?v=mr1FMrwi6Ew&amp;t=2780" rel="nofollow noreferrer">https://www.youtube.com/watch?v=mr1FMrwi6Ew&amp;t=2780</a></p>

CC BY-SA 4.0
2021-02-15T06:31:23.507Z
2021-02-15T06:31:23.507Z
user3209423940248
<p>Has the variant of the Set Cover problem where each set is of size at most <span class="math-container">$d$</span>, for some given <span class="math-container">$d$</span>, been studied? Is it polynomial-time solvable for <span class="math-container">$d=2$</span> and NP-hard for <span class="math-container">$d=3$</span> like SAT?</p>

<np-hardness><set-cover>
Set cover with small subsets
user61376
# Set cover with small subsets

(Asked by: username_0 on 2021-02-14)

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?

**Tags:** np-hardness, set-cover


---

## 1 answers

### Answer by username_1 on 2021-02-15. Score: 3

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>


---

