2
$\begingroup$

Are there any NP-hard problems that are considered kind of the standard for reductions? There's so many but it feels like some come up more often than others (for example Vertex Cover, Independent Set, 3-SAT, etc.). I'm sure people just pick whatever is most convenient, but where's the boundary between "more useful" and "too obscure" when choosing a problem to reduce from?

$\endgroup$
2
$\begingroup$

Most textbooks will have a set of 'core' NP-Complete problems from which all their examples and exercises would reduce from, which are probably the ones you list (3SAT, Vertex Cover, Independent Set, Clique, k-Coloring, Set Cover, Dominating Set, Hitting Set, Subset Sum, Knapsack.)

A bigger set of 'standard' problems would be Garey & Johnson's book. Beyond that, people look at hard restrictions of the standard problems (i.e. k-coloring for k=3, Exact Cover version of set cover, not-all-equal 3SAT, etc).

Beyond that, it gets fairly domain specific.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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