Computers and Intractability
This work is in three parts. The first introduces NP completeness and describes how to go about proving that a problem is NP complete. The second part looks at more advanced topics, such as the structure of the class of NP problems - you might think of all NP complete problems as being more or less the same, but the authors show that there is more it than that. They also describe tractable ways of obtaining approximate solutions to NP complete problems.
It's the third part which will be the most important for most people though. This consists of a list of a large number of NP complete problems including references to the proof of their NP completeness. So whether you are you are a student of computational complexity, you are thinking of attacking the million dollar P=NP question, or you just have to write a program for a problem which you think might be NP complete, you will find that this book is a useful addition to your library.