A concise list of NP-complete problems

May 10, 2013

A major part of higher-level computer science courses is the exploration of computational complexity theory. When you encounter a problem you must prove is NP-complete, it helps to have a repertoire of known NP-complete problems. The following is a list of the problems I have found to be most useful when crafting polynomial time reductions.

Recall that the decision version of a computationally difficult problem is in the complexity class NP when there exists a polynomial-time algorithm to verify a solution and return yes or no (or, equivalently, when there exists a non-deterministic Turing machine that can return yes given only the instance of the problem, in polynomial time).

The problems in this list are all NP-complete, which means that every other problem in NP can be transformed into an instance of one of these by a polynomial-time reduction.

This is by far not a representative example of all NP-complete problems. Wikipedia has a larger list, but its list is still incomplete.

Covering and packing problems

Covering and packing problems have the flavor of constructing a subset or subsets of a given set of objects, with the following constraints, respectively: choose as few objects as possible to form a subset that satisfies a condition, and choose as many objects as possible while avoiding a conflict.

Notice that the covering problems (set cover and vertex cover) contain restrictions like “at most k subsets” or “at most k vertices.” Identifying these phrases in the problem you must show is NP-complete can narrow your search for an appropriate known NP-complete problem.

In packing problems, the restriction is reversed: a solution must contain “at least k” objects.

The hybrid covering-packing problem

I like to think of the three-dimensional matching problem as a hybrid between covering and packing: given three sets A, B, and C such that none of the sets share any elements, and a set X of triples of the form (a, b, c) where a is drawn from A, b is drawn from B, and c is drawn from C, find a subset S of X such that all of the elements from A, B, and C appear once in S, in any triple. The decision version asks if there exists a solution set S of size exactly k.

Three-dimensional matching is a covering problem because the goal is to ensure that all elements of A, B, and C appear in the final set, but it is also a packing problem due to the fact that no two triples in the final solution can contain the same element.

Path and cycle problems

Path and cycle problems involve finding a path or cycle in a graph that satisfies a given property.

Sum and weight problems

Sum and weight problems are like covering and packing problems, but have solutions that must sum or be weighed to achieve a target value.