I wonder whether there is a website or a survey collecting all known NP-complete or NP-hard problems on graph theory?
$\begingroup$
$\endgroup$
4
-
7$\begingroup$ "All known problems" is asking a lot... $\endgroup$– Sam HopkinsCommented Nov 11, 2021 at 12:58
-
4$\begingroup$ By the way, there is a stackexchange for theoretical computer science (: $\endgroup$– exfretCommented Nov 11, 2021 at 23:37
-
2$\begingroup$ I would guess not, because it is fairly straightforward to invent new NP-complete / NP-hard graph theory problems; e.g. arxiv.org/abs/2001.04120 $\endgroup$– Per AlexanderssonCommented Nov 12, 2021 at 9:04
-
$\begingroup$ Somewhat related question at cstheory.SE: cstheory.stackexchange.com/q/4784/2367 $\endgroup$– Hermann GruberCommented Nov 21, 2021 at 21:47
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
Here is a section on graph theory in A compendium of NP optimization problems by P. Crescenzi and V. Kann.
answered Nov 11, 2021 at 14:50
$\begingroup$
$\endgroup$
A site dedicated to graph classes, including the computational complexity of associated problems, is
answered Nov 11, 2021 at 12:25
$\begingroup$
$\endgroup$
2
https://en.wikipedia.org/wiki/List_of_NP-complete_problems $$ \quad\quad\quad\quad\quad\quad\quad\quad $$
-
2$\begingroup$ That both has non-graph theory problems and also doesn't seem to include every NP-complete graph theory problem. So not quite what the question is asking for. $\endgroup$– JoshuaZCommented Nov 11, 2021 at 12:19
-
1$\begingroup$ A plus point is that the wikipedia list is both curated and regularly updated, in contrast to the list by Crescenzi and Kann - which has been discontinued in the 2000s. It's good to have those resources at hand when you're trying to establish NP-hardness of some graph problem. In my own research, I have successfully made use of the original Garey & Johnson 1979 list, which seems to be among the first of that kind. $\endgroup$ Commented Nov 21, 2021 at 21:41