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