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 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*.

**Independent set.**For a given graph*G*= (*V*,*E*), is there a subset*V′*of size at least*k*of the vertices of*G*such that there exists no edges between any two chosen vertices in*V′*? The term*independent*is derived from the idea that vertices in*V′*are independent when they share no edges.**Set cover.**For a*universe**U*of objects, and a set*A*of subsets of*U*, are there*k*subsets from*A*such that the union of them all equals*U*? The term*cover*conveys the idea that the union of all sets in a solution covers all of the objects in*U*.**Vertex cover.**For a given graph*G*= (*V*,*E*), is there a subset*V′*of*V*of size at most*k*such that, for all vertices*v*in*V′*, removing*v*and its edges from*G*results in a graph no longer containing edges? The term*cover*conveys the idea that each vertex in*V′*manages to cover all the edges in*E*.

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.

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 involve finding a path or cycle in a graph that satisfies a given property.

**Travelling salesman problem.**Given a directed, weighted graph*G*= (*V*,*E*), whose weights correspond to distances (say, on a map), is there a*simple cycle*(a cycle with no repeating vertices) such that the cycle touches all vertices in the graph and the sum of all the weights of the cycle is at most*k*? A hallmark of computer science, the travelling salesman problem is one of the most well-studied problems, probably due to it having many practical applications.**Hamiltonian cycle.**A generalization of the travelling salesman problem above, in which it must be determined that there exists a simple cycle in a directed graph such that the cycle contains all vertices in the graph.

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

**Knapsack problem.**Given a set of objects, each associated with a value and weight, is there a subset of objects whose combined weight is less than or equal to a target value*k*, while maximizing the value of the chosen objects? A variant of the problem considers both the value and weight, specifying a minimum value that must be achieved as well as a maximum weight that must not be exceeded.**Subset sum.**Given a set*X*of numbers, is there some subset*S*of*X*such that the sum of all numbers in*S*equals a target value*k*? Subset sum is a good example of a difficult problem, because it is difficult to imagine an improvement over enumerating all possible subsets of*X*to find a solution.**Number partition problem.**A notable problem that is an extension of subset sum, this problem asks if there are two subsets of a given set*X*such that the difference of the sum of both subsets equals a target value*k*. The difference of the sum of these two sets is referred to as the*residue*. The simple variation of the problem specifying that the residue must equal zero also exists.