Is there a good source to find various decision problems on graph and networks? For a project I'm doing it'd be useful to be able to look at lots of different problems. Is there a good source for finding them?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
A general list of NP-complete problems can be found in Garey & Johnson's book "Computers and Intractability". It contains an appendix that lists roughly 300 NP-complete problems, and despite its age is often suggested when one wants a list of NP-complete problems.
I haven't read the book, but based on its reputation it would be a quite good start to any investigation.
$\begingroup$
$\endgroup$
You may also have a look at the Compendium of Parameterized Problems by Marco Cesati (http://cesati.sprg.uniroma2.it/research/compendium/) which contains a list of many hard graph problems. The compendium deals with the parameterized complexity of these problems for various parameterizations and the list of results is partially outdated by now but since parameterized algorithmics deals mostly with NP-hard problems, almost all of the the problems in this compendium are NP-hard, even if this is not stated explicitly.
answered Feb 12, 2020 at 8:16