<p>A general list of NP-complete problems can be found in Garey &amp; 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.</p>

<p>I haven't read the book, but based on its reputation it would be a quite good start to any investigation.</p>

CC BY-SA 4.0
2020-02-11T22:25:19.700Z
2020-02-12T08:29:53.193Z
2020-02-12T08:29:53.193Z
Mark Schultz-Wu
<p>You may also have a look at the Compendium of Parameterized Problems by Marco Cesati (<a href="http://cesati.sprg.uniroma2.it/research/compendium/" rel="noreferrer">http://cesati.sprg.uniroma2.it/research/compendium/</a>) 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.</p>

CC BY-SA 4.0
2020-02-12T08:16:32.890Z
2020-02-12T08:16:32.890Z
Christian Komusiewicz
<p>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?</p>

<graph-theory><np>
List of NP-Complete graph problems/ properties?
Samuel Barr
# List of NP-Complete graph problems/ properties?

(Asked by: username_0 on 2020-02-11)

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?

**Tags:** graph-theory, np

---

## 2 answers

### Answer by username_1 on 2020-02-11. Score: 8 | Accepted answer

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.


---

### Answer by username_2 on 2020-02-12. Score: 5

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.


---

