Published in 1979, this book, or Garey and Johnson for short (after
the authors), is the definitive book on NP-completeness. I personally
like to call this book the little black book of NP-completeness,
because it's smaller than most computer science textbooks, has a black
cover, and one of the appendices (and the reason most people use the
book) is a listing of NP-complete problems and where to find the
proofs of their NP-completeness.
NP-Completeness
The book opens with a description of why NP-completeness is such a
useful concept. It turns out that it's very difficult to prove that a
given problem is guaranteed to take a computer a long time to solve.
There is, however, a class of problems (the ones that are NP-complete)
that are provably equivalently difficult to solve. Since nobody has
yet found a good algorithm (defined here as one that runs in
polynomial time), it's probably not worth working on finding a good
algorithm to solve the problem exactly because so many
smart people have already tried and failed.
A brief outline of the book
The first chapter goes on to define mathematically what is meant by a
problem, algorithm, and the complexity of those algorithms. They
discuss the fact that greater than polynomial time algorithms tend to
be inefficient solutions (there's a table showing how long it will take
to solve various problems, showing that exponential problems can take
centuries to solve even if they're not very large problems, while
polynomial problems can usually be solved in minutes or seconds.)
The second chapter brings out the heavy machinery. Here we get a proof
of Cook's Theorem, that satisfiability is NP-complete.
(Satisfiability is the problem of whether there exists an assignment to
boolean variables that satisfies a set of boolean equations). This
is an important result, because the typical way to prove that a problem
is NP-complete is to show that an existing NP-complete problem is
equivalent to it. All NP-completeness proofs can be traced back to the
fact that satisfiability is NP-complete. In order to get this far,
first they introduce the concepts of languages and Turing machines,
and describe how they're a good model for computation.
Chapter three shows how to prove that a problem is NP-complete. The
authors discuss six basic problems which have historically been useful
to prove many other problems NP-complete. In theory, it's possible to
show that any NP-complete problem is equivalent to every other problem,
but some of them have much easier transformations.
In the fourth chapter, the authors introduce the concept of strong
NP-completeness, and the fact that there is a hierarchy of problem
complexities. We also see an example of a pseudo-polynomial time
algorithm: an algorithm which can solve a problem in some variable other
than the problem size. (An example of this is the partition problem:
if we are trying to find a subset of objects that have a certain size,
the problem is much easier if we're guaranteed that the objects are all
small.) The practical upshot of this is that even though some problems
are NP-complete, there are still efficient ways to solve them in some
circumstances.
The fifth chapter discusses the concept of NP-hardness, as well as
discussing the literature and terminology that was used to discuss
NP-complete problems.
Chapter six introduces the concept of approximation algorithms. In
many cases, it's difficult to solve the problem in the most efficient
way, but it's easy to find a solution that's good enough (for the right
definition of "good enough"...)
The last chapter of the book discusses various other problem
classifications. NP-completeness deals with the time complexity of
problems, where as PSPACE-completeness deals with the amount of memory
it takes to solve a problem. They discuss various other classes of
problems, such as #P and log-space, and end by discussing the
question of P vs. NP.
Nearly half the book is given over to a listing of NP-complete problems,
categorized according to problem domain. If you ever need to prove a
problem NP-complete, look there for a problem similar to yours. (Who
knows? It might even be there already...) Each problem has a
description of what an instance of the problem looks like, what
question the problem wants answered, a reference to the proof that
showed its NP-completeness, and some comments which generally discuss
related problems.