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.

  • 3
    $\begingroup$ For individual results, it is better to cite the original article than to cite a book or a webpage which gathers many related results. $\endgroup$ – Tsuyoshi Ito Apr 3 '11 at 20:19
  • 2
    $\begingroup$ Or you can cite a survey paper (if it exists) on a particular subject, for example "A survey of NP-complete puzzles" (cs.wmich.edu/~elise/courses/cs431/icga2008.pdf) $\endgroup$ – Marzio De Biasi Apr 3 '11 at 21:11
  • $\begingroup$ 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! $\endgroup$ – Jay Apr 3 '11 at 22:17

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

  • 1
    $\begingroup$ 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. $\endgroup$ – Marzio De Biasi Apr 3 '11 at 20:54
  • 3
    $\begingroup$ because not all decision problems have natural approximation variants. $\endgroup$ – Suresh Venkat Apr 3 '11 at 21:49
  • $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Apr 3 '11 at 22:58
  • $\begingroup$ 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). $\endgroup$ – Jay Apr 4 '11 at 10:55
  • $\begingroup$ 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. $\endgroup$ – Saeed Dec 7 '11 at 19:48

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



I know you want book, but I think in this case Wiki 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, and I think this new problems (and newer) just available on web and papers not books.

  • $\begingroup$ It looks like that list has less than 100 problems, so much less than the Viggo Compendium mentioned in other answers... $\endgroup$ – einpoklum - reinstate Monica Dec 4 '13 at 20:14
  • $\begingroup$ @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). $\endgroup$ – Saeed Dec 4 '13 at 23:41

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.