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
Related Tags
np-hardness × 608cc.complexity-theory × 315
graph-theory × 95
reference-request × 71
graph-algorithms × 62
ds.algorithms × 58
reductions × 43
complexity-classes × 41
approximation-algorithms × 38
optimization × 38
np-complete × 34
approximation-hardness × 32
sat × 31
np × 22
co.combinatorics × 17
partition-problem × 16
set-cover × 14
subset-sum × 13
packing × 13
polynomial-time × 12
counting-complexity × 11
graph-colouring × 11
cg.comp-geom × 10
directed-acyclic-graph × 10
time-complexity × 9