<p>There is "Encyclopedia of Algorithms" from 2008, which surveys a <em>lot</em> of different problems (1160 pages of it)</p>

<p><a href="http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1" rel="noreferrer">http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1</a></p>

CC BY-SA 2.5
2011-04-07T06:46:51.267Z
2011-04-07T06:46:51.267Z
Nathann Cohen
<p>I know you want book, but I think in this case <a href="http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Mathematical_programming" rel="nofollow">Wiki</a> is good, You can download it with depth 2 to have list of problems and their definition, Also I think Gary and Johnson book is good enough to be familiar with problems, after that you just should find your interest and work on it, there is no need to know all problems and their solution. Also reading first papers of your interest problem is good, you can find what was the first idea, after that may be solutions become better, and in books you will find best solution not philosophy of solution. </p>

<p>Also there are some new problems like matroid secretary See <a href="http://www.cs.cornell.edu/~rdk/papers/matsec.pdf" rel="nofollow">this</a>, and I think this new problems (and newer) just available on web and papers not books.</p>

CC BY-SA 3.0
2013-12-04T20:14:20.720Z
It looks like that list has less than 100 problems, so much less than the Viggo Compendium mentioned in other answers...
einpoklum
CC BY-SA 3.0
2013-12-04T23:41:24.910Z
@einpoklum, I count the number of general problems in wiki link, it's slightly bigger than 100, also many of them have many varitions and because of this I suggested to download in depth two. And more important than this two is wiki is open and can be edited and updated by new generation of problems, the main reason that I mention it is this. Finally I doubt that in usual compendiom anyone write about hardness of some interesting games like tetris, mario, ... which are mentioned in wiki. (I mean quantity does not mean domination).
Saeed
CC BY-SA 2.5
2011-04-04T06:32:43.343Z
2011-04-04T06:32:43.343Z
Saeed
<p>The book <a href="http://www.csc.kth.se/~viggo/approxbook/">http://www.csc.kth.se/~viggo/approxbook/</a> on which the site <a href="http://www.csc.kth.se/~viggo/wwwcompendium/">http://www.csc.kth.se/~viggo/wwwcompendium/</a> is based. </p>

CC BY-SA 2.5
2011-04-03T20:54:43.680Z
I took a look at the site and the G&J's book still rules; for example "games and puzzles": G&J 15 problems, csc.kth.se 2 problems; "Automata and language theory": G&J 21 problems, csc.kth.se 5 problems.
Marzio De Biasi
CC BY-SA 2.5
2011-04-03T21:49:04.363Z
because not all decision problems have natural approximation variants.
Suresh Venkat
CC BY-SA 2.5
2011-04-03T22:58:28.290Z
@Suresh: you're right, I completely missed the "about the approximate solution of NP-hard combinatorial optimization problems" of the book (I only gave a fast look at the list).
Marzio De Biasi
CC BY-SA 2.5
2011-04-04T10:55:11.660Z
Thanks a lot -- now I can cite both G&J and this book (I knew their online compendium, but I didn't know it had become a book).
Jay
CC BY-SA 3.0
2011-12-07T19:48:47.697Z
At least web compendium is not update and I think it's age is around G&J book age, for example sparsest cut problem, I think in 1986 proved that it is NP-Hard, but this compendium doesn't mentioned it.
Saeed
CC BY-SA 2.5
2011-04-03T20:15:14.260Z
2011-04-03T20:15:14.260Z
Mateus de Oliveira Oliveira
<p>Is there some book or other reference that I can cite as a catalog of NP-complete problems, more up-to-date than the appendix of Garey&amp;Johnson's book? I don't want to cite web sites, even though I know there are some excellent compendiums om the web.</p>

CC BY-SA 2.5
2011-04-03T20:19:12.780Z
For individual results, it is better to cite the original article than to cite a book or a webpage which gathers many related results.
Tsuyoshi Ito
CC BY-SA 2.5
2011-04-03T21:11:57.217Z
Or you can cite a survey paper (if it exists) on a particular subject, for example "A survey of NP-complete puzzles" (http://www.cs.wmich.edu/~elise/courses/cs431/icga2008.pdf)
Marzio De Biasi
CC BY-SA 2.5
2011-04-03T22:17:18.410Z
I'd like to point the reader to "more NP-complex problems", not being specific -- so I think the book by Ausiello and others seems like a good option. I'll also cite the survey papers, of course!
Jay
<cc.complexity-theory><reference-request><np-hardness>
Catalog of NP-complete problems, more up-to-date than Garey&Johnson?
Jay
# Catalog of NP-complete problems, more up-to-date than Garey&Johnson?

(Asked by: username_0 on 2011-04-03)

Is there some book or other reference that I can cite as a catalog of NP-complete problems, more up-to-date than the appendix of Garey&Johnson's book? I don't want to cite web sites, even though I know there are some excellent compendiums om the web.

**Tags:** cc.complexity-theory, reference-request, np-hardness
> **Comments:**
> **username_1**: For individual results, it is better to cite the original article than to cite a book or a webpage which gathers many related results.  
> **username_2**: Or you can cite a survey paper (if it exists) on a particular subject, for example "A survey of NP-complete puzzles" (http://www.cs.wmich.edu/~elise/courses/cs431/icga2008.pdf)  
> **username_0**: I'd like to point the reader to "more NP-complex problems", not being specific -- so I think the book by Ausiello and others seems like a good option. I'll also cite the survey papers, of course!  

---

## 3 answers

### Answer by username_6 on 2011-04-03. Score: 8 | Accepted answer

The book <http://www.csc.kth.se/~viggo/approxbook/> on which the site <http://www.csc.kth.se/~viggo/wwwcompendium/> is based.

> **Comments:**
> **username_2**: I took a look at the site and the G&J's book still rules; for example "games and puzzles": G&J 15 problems, csc.kth.se 2 problems; "Automata and language theory": G&J 21 problems, csc.kth.se 5 problems.  
> **username_7**: because not all decision problems have natural approximation variants.  
> **username_2**: @Suresh: you're right, I completely missed the "about the approximate solution of NP-hard combinatorial optimization problems" of the book (I only gave a fast look at the list).  
> **username_0**: Thanks a lot -- now I can cite both G&J and this book (I knew their online compendium, but I didn't know it had become a book).  
> **username_4**: At least web compendium is not update and I think it's age is around G&J book age, for example sparsest cut problem, I think in 1986 proved that it is NP-Hard, but this compendium doesn't mentioned it.  

---

### Answer by username_3 on 2011-04-07. Score: 5

There is "Encyclopedia of Algorithms" from 2008, which surveys a *lot* of different problems (1160 pages of it)

<http://www.springer.com/computer/theoretical+computer+science/book/978-0-387-30770-1>


---

### Answer by username_4 on 2011-04-04. Score: 2

I know you want book, but I think in this case [Wiki](http://en.wikipedia.org/wiki/List_of_NP-complete_problems#Mathematical_programming) is good, You can download it with depth 2 to have list of problems and their definition, Also I think Gary and Johnson book is good enough to be familiar with problems, after that you just should find your interest and work on it, there is no need to know all problems and their solution. Also reading first papers of your interest problem is good, you can find what was the first idea, after that may be solutions become better, and in books you will find best solution not philosophy of solution.

Also there are some new problems like matroid secretary See [this](http://www.cs.cornell.edu/~rdk/papers/matsec.pdf), and I think this new problems (and newer) just available on web and papers not books.

> **Comments:**
> **username_5**: It looks like that list has less than 100 problems, so much less than the Viggo Compendium mentioned in other answers...  
> **username_4**: @einpoklum, I count the number of general problems in wiki link, it's slightly bigger than 100, also many of them have many varitions and because of this I suggested to download in depth two. And more important than this two is wiki is open and can be edited and updated by new generation of problems, the main reason that I mention it is this. Finally I doubt that in usual compendiom anyone write about hardness of some interesting games like tetris, mario, ... which are mentioned in wiki. (I mean quantity does not mean domination).  

---

