Other NP-Complete Problems

Clique, vertex cover, and integer programming are just three of the literally hundreds of problems that have been shown to be NP-complete. It is important to be aware of which kinds of problems tend to be hard, so you recognize them when you see them in applications, and also to provide a suitable class of candidates for future reductions. Some, but by no means all, of the hard problems from the catalog include:

• Integer partition - Can you partition n integers into two subsets such that the sums of the subsets are equal? See Section for details.
• Bin packing - How many bins of a given size do you need to hold n items of variable size? See Section for details.
• Chromatic number - How many colors do you need to color a graph such that no neighboring vertices are of the same color? See Section for details.
• Bandwidth - Which permutation p of the vertices of a graph minimizes the length of the longest edge when the vertices are ordered on a line, i.e. ? See Section for details.

A few other catalog problems exist in a limbo state, where it is not known whether the problem has a fast algorithm or is NP-complete. The most prominent of these are graph isomorphism (see Section ) and primality testing (see Section ). That this limbo list is so short is quite a tribute to the state of the art in algorithm design and the power of NP-completeness. For almost every important problem for which we do not know a fast algorithm, we have a good solid reason for why one doesn't exist.

The same should hold true for the problems you encounter in your work. One way or another they should be resolved as being either hard or polynomial. Leaving them in a limbo state is a sure sign of a bush-league algorithm designer.

It takes experience to be able to sense whether a problem is likely to be hard or not. Perhaps the quickest way to gain this experience is through careful study of the catalog. Note that slightly changing the wording of a problem can make the difference between it being polynomial or NP-complete. Finding the shortest path in a graph is easy, while finding the longest path in a graph is hard. Constructing a tour that visits all the edges once in a graph is easy, while constructing a tour that visits all the vertices once is hard.

The first thing to do when you suspect a problem might be NP-complete is look in Garey and Johnson's book Computers and Intractability [GJ79], which contains a list of several hundred problems known to be NP-complete. Likely you will find the problem you are interested in.