Monthly Archives: June 2014

In 1979, Garey&Johnson published  the classic work: Computers and Intractability: A Guide to the Theory of NP-Completeness.  It’s a fantastic book, that every Computer Scientist should own.  The first half of the book describes the theory of NP-Completeness, and shows methods to prove problems NP-Complete.  The last 100 pages list out NP-Complete problems, with a short description of why it’s NP-Complete, along with some other facts.

I teach Computer Science at Ohio Wesleyan University, and one of the courses I regularly teach is our upper-level Analysis of Algorithms class.  One of the subjects in this class is NP-Completeness, and I have students do some reductions on homeworks and tests.  I use the Garey&Johnson book to help me find problems, but when I do, I run across several issues:

1) The book was published in 1979, and many more problems have been discovered since then.

2) For most problems, the authors do not provide a proof of NP-Completeness, just a description of the problem they are reducing from, with a reference to the paper the reduction was made in.  Sometimes, even the reference is missing.

Fixing issue #1 is beyond my ability, though I would dearly love an updated version of this book.  (Though in truth, a modern list of NP-Complete problems would probably be larger than any physical book could contain).  As a teacher, though, issue #2 was an even greater challenge.  When I’m looking for a problem to assign on a homework or test, I’m usually time-constrained (I teach this topic at the end of the semester, when lots of demands are on my time), and I need to determine relatively quickly how hard the reduction will be for the students.  This has proven difficult for me, and I wondered if maybe it was difficult for other faculty as well.

Thus,  I have decided to spend some time building this resource.  The goal is for this to be an ongoing project, where I (eventually, probably over the course of years) go through this book, problem by problem, and for each proof that is not done in the book, provide:

• A description of the problem
• A quick sketch of how the reduction will go (this is basically the first step of the proof- where we convert an instance of a known NP-Complete problem to an instance of our problem.)  I find this to be the most difficult, “flash of insight” driven part of the proof.  Hopefully by providing this part, the rest of the proof will fall into place.
• A ranking of difficulty from 1 (trivial) to 10 (basically impossible to be done by a student just learning this for the first time).  In my classes, I tend to find problems in the 3-6 range to be good choices

Hopefully, this will become a resource for faculty.  I plan on password-protecting older entries so that students can’t find solutions by searching the web.

I fully expect to make mistakes, to have ratings the people disagree with, for other people to find more elegant and simpler reductions, and so on.  Please let me know if any of that happens!

This is not meant to be a place to teach basic NP-Completeness (what a reduction is, why we care about it, anything like that).  That stuff is important, but Garey&Johnson teach it well 🙂

I’ll start with a quick overview of the problems proved in the early part of the book, because they form the “core” from which most of the reductions are based.