This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are hundreds of such problems known, this list is in no way comprehensive. Many problems of this type can be found in Garey & Johnson (1979).
Graphs and hypergraphs
Graphs occur frequently in everyday applications. Examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (e.g. Facebook or LinkedIn).
1-planarity
3-dimensional matching
Bipartite dimension
Capacitated minimum spanning tree
Route inspection problem (also called Chinese postman problem) for mixed graphs (having both directed and undirected edges). The program is solvable in polynomial time if the graph has all undirected or all directed edges. Variants include the rural postman problem.
Clique problem
Complete coloring, a.k.a. achromatic number
Domatic number
Dominating set, a.k.a. domination number
Bandwidth problem
Clique cover problem
Rank coloring a.k.a. cycle rank
Degree-constrained spanning tree
Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).
Feedback vertex set
Feedback arc set
Graph homomorphism problem
Graph coloring
Graph partition into subgraphs of specific types (triangles, isomorphic subgraphs, Hamiltonian subgraphs, forests, perfect matchings) are known NP-complete. Partition into cliques is the same problem as coloring the complement of the given graph. A related problem is to find a partition that is optimal terms of the number of edges between parts.
Hamiltonian completion
Hamiltonian path problem, directed and undirected.
Longest path problem
Maximum bipartite subgraph or (especially with weighted edges) maximum cut.
Maximum independent set
Maximum Induced path
Graph intersection number
Metric dimension of a graph
Minimum k-cut
Minimum spanning tree, or Steiner tree, for a subset of the vertices of a graph. (The minimum spanning tree for an entire graph is solvable in polynomial time.)
Pathwidth
Set cover (also called minimum cover problem) This is equivalent, by transposing the incidence matrix, to the hitting set problem.
Set splitting problem
Shortest total path length spanning tree
Slope number two testing
Treewidth
Vertex cover
3-partition problem
Bin packing problem
Knapsack problem, quadratic knapsack problem, and several variants
Variations on the Traveling salesman problem. The problem for graphs is NP-complete if the edge lengths are assumed integers. The problem for points on the plane is NP-complete with the discretized Euclidean metric and rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.
Bottleneck traveling salesman
Integer programming. The variant where variables are required to be 0 or 1, called zero-one linear programming, and several other variants are also NP-complete
Numerical 3-dimensional matching
Partition problem
Quadratic assignment problem
Quadratic programming (NP-hard in some cases, P if convex)
Subset sum problem
Closest string
Longest common subsequence problem
The bounded variant of the Post correspondence problem
Shortest common supersequence
String-to-string correction problem
Games and puzzles
Battleship
Bejeweled
Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself.
Candy Crush Saga
Donkey Kong
Eternity II
(Generalized) FreeCell
Fillomino
Hashiwokakero
Heyawake
(Generalized) Instant Insanity
Kakuro (Cross Sums)
Kuromasu (also known as Kurodoko)
Legend of Zelda
Lemmings
Light Up
Masyu
Metroid
Minesweeper Consistency Problem (but see Scott, Stege, & van Rooij)
Nimber (or Grundy number) of a directed graph.
Nonograms
Nurikabe
Pokémon
SameGame
Slither Link on a variety of grids
(Generalized) Sudoku
Super Mario Bros
Problems related to Tetris
Verbal arithmetic
Art gallery problem and its variations.
Berth allocation problem
Betweenness
Assembling an optimal Bitcoin block.
Boolean satisfiability problem (SAT). There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals (3SAT), since it is used in the proof of many other NP-completeness results.
Conjunctive Boolean query
Cyclic ordering
Circuit satisfiability problem
Uncapacitated Facility Location
Flow Shop Scheduling Problem
Generalized assignment problem
Upward planarity testing
Hospitals-and-residents problem with couples
Some problems related to Job-shop scheduling
Monochromatic triangle
Minimum maximal independent set a.k.a. minimum independent dominating set
Maximum common subgraph isomorphism problem
Minimum degree spanning tree
Minimum k-spanning tree
Metric k-center
Maximum 2-Satisfiability
Modal logic S5-Satisfiability
Some problems related to Multiprocessor scheduling
Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger m x n matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.
Minimal addition chains for sequences. The complexity of minimal addition chains for individual numbers is unknown.
Non-linear univariate polynomials over GF[2n], n the length of the input. Indeed, over any GF[qn].
Open-shop scheduling
Pathwidth, or, equivalently, interval thickness, and vertex separation number
Pancake sorting distance problem for strings
k-Chinese postman
Subgraph isomorphism problem
Variations of the Steiner tree problem. Specifically, with the discretized Euclidean metric, rectilinear metric. The problem is known to be NP-hard with the (non-discretized) Euclidean metric.
Set packing
Serializability of database histories
Scheduling to minimize weighted completion time
Sparse approximation
Block Sorting (Sorting by Block Moves)
Second order instantiation
Treewidth
Testing whether a tree may be represented as Euclidean minimum spanning tree
Three-dimensional Ising model
Vehicle routing problem
