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

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

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