Despite that 23 years have passed since its publication, I consider Garey and Johnson the single most important book on my office bookshelf. Every computer scientist should have this book on their shelves as well. NP-completeness is the single most important to come out of theoretical computer science and no book covers it as well as Garey and Johnson.
The popularity of the book comes mainly from its appendix that consumes nearly half the pages. This section gives a comprehensive list of NP-complete problems in a well-structured and organized fashion. If one needs to determine whether a problem X is NP-complete, one can almost always either find X in the appendix or find a Y in the appendix that easily reduces to X. And the name-instance-question format has inspired many imitators, for example P-completeness and NP optimization.
It would be a mistake to ignore the first half of the book. Garey and Johnson has the best introduction to computational complexity I have ever seen. It gives basic proofs of NP-completeness results but more importantly gives the tools one needs to generate new NP-complete proofs. Section 6 discusses issues about what to do if one has to write an algorithm for an NP-complete problem. Section 7 discusses many different advanced concepts in complexity that give a taste to the richness of the area. And don't miss the terminological history in Section 5.2.
Of course Garey and Johnson misses the last 23 years of research. Many more NP-complete problems are known. Linear Programming and Composite Number are listed as open questions. The results on hardness of approximation based on probabilistically checkable proofs came long after the publication of the book. Section 7, "Beyond NP-completeness" is woefully out of date. Nevertheless no book before or since has captured the critical NP-completeness concept better than this classic book.
