New answers tagged np-hardness
2
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 ...
Top 50 recent answers are included
