List of NP-complete problems

Graphs and hypergraphs

• 1-planarity
• 3-dimensional matching
• Bipartite dimension
• Capacitated minimum spanning tree
• Route inspection problem for mixed graphs. 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.
• Feedback vertex set
• Feedback arc set
• Graph homomorphism problem
• Graph coloring
• Graph partition into subgraphs of specific types 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 maximum cut.
• Maximum independent set
• Maximum Induced path
• Graph intersection number
• Metric dimension of a graph
• Minimum k-cut
• Steiner tree, or Minimum spanning tree for a subset of the vertices of a graph.
• Modularity maximization
• Pathwidth
• Set cover 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

  Mathematical programming

• 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 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
• Latin squares
• Numerical 3-dimensional matching
• Partition problem
• Quadratic assignment problem
• Solving two-variable quadratic polynomials over the integers. Given positive integers, find positive integers such that
• Quadratic programming
• Subset sum problem

  Formal languages and string processing

• Closest string
• Longest common subsequence problem over multiple sequences
• The bounded variant of the Post correspondence problem
• Shortest common supersequence
• String-to-string correction problem

  Games and puzzles

• Battleship
• Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself.
• Eternity II
• FreeCell
• Fillomino
• Hashiwokakero
• Heyawake
• Instant Insanity
• Kakuro
• Kingdomino
• Kuromasu
• LaserTank
• Lemmings
• Light Up
• Masyu
• Minesweeper Consistency Problem
• Nimber of a directed graph.
• Numberlink
• Nonograms
• Nurikabe
• NxNxN Rubik's Cube
• Pandemic
• SameGame
• Set
• Slither Link on a variety of grids
• Sudoku
• Problems related to Tetris
• Verbal arithmetic

  Other

• Berth allocation problem
• Betweenness
• Assembling an optimal Bitcoin block.
• Boolean satisfiability problem. There are many variations that are also NP-complete. An important variant is where each clause has exactly three literals, since it is used in the proof of many other NP-completeness results.
• Conjunctive Boolean query
• Cyclic ordering
• Circuit satisfiability problem
• Uncapacitated facility location problem
• 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, n the length of the input. Indeed, over any GF.
• 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 Euclidean metric.
• Set packing
• Serializability of database histories
• Scheduling to minimize weighted completion time
• Sparse approximation
• Block Sorting
• Second order instantiation
• Treewidth
• Testing whether a tree may be represented as Euclidean minimum spanning tree
• Three-dimensional Ising model
• Vehicle routing problem