List of NP-complete problems

Template:Short description Template:Use dmy dates Script error: No such module "Hatnote".

This is a list of some of the more commonly known problems that are NP-complete when expressed as decision problems. As there are thousands of such problems known, this list is in no way comprehensive. Many problems of this type can be found in Template:Harvtxt.

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 Template:Sfnp
3-dimensional matching^[1]^[2]Template:Rp
Bandwidth problem^[2]Template:Rp
Bipartite dimension^[2]Template:Rp
Capacitated minimum spanning tree^[2]Template:Rp
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.^[2]Template:Rp
Clique cover problem^[1]^[2]Template:Rp
Clique problem^[1]^[2]Template:Rp
Complete coloring, a.k.a. achromatic number^[2]Template:Rp
Cycle rank
Degree-constrained spanning tree^[2]Template:Rp
Domatic number^[2]Template:Rp
Dominating set, a.k.a. domination number^[2]Template:Rp

NP-complete special cases include the edge dominating set problem, i.e., the dominating set problem in line graphs. NP-complete variants include the connected dominating set problem and the maximum leaf spanning tree problem.^[2]Template:Rp

Feedback vertex set^[1]^[2]Template:Rp
Feedback arc set^[1]^[2]Template:Rp
Graph coloring^[1]^[2]Template:Rp
Graph homomorphism problem^[2]Template:Rp
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.^[2]Template:Rp
Grundy number of a directed graph.^[2]Template:Rp
Hamiltonian completion^[2]Template:Rp
Hamiltonian path problem, directed and undirected.^[1]^[2]Template:Rp
Induced subgraph isomorphism problem
Graph intersection number^[2]Template:Rp
Longest path problem^[2]Template:Rp
Maximum bipartite subgraph or (especially with weighted edges) maximum cut.^[1]^[2]Template:Rp
Maximum common subgraph isomorphism problem^[2]Template:Rp
Maximum independent set^[2]Template:Rp
Maximum Induced path^[2]Template:Rp
Minimum maximal independent set a.k.a. minimum independent dominating set^[3]

NP-complete special cases include the minimum maximal matching problem,^[2]Template:Rp which is essentially equal to the edge dominating set problem (see above).

Metric dimension of a graph^[2]Template:Rp
Metric k-center
Minimum degree spanning tree
Minimum k-cut
Minimum k-spanning tree
Minor testing (checking whether an input graph $G$ contains an input graph $H$ as a minor); the same holds with topological minors
Steiner tree, or Minimum spanning tree for a subset of the vertices of a graph.^[1] (The minimum spanning tree for an entire graph is solvable in polynomial time.)
Modularity maximization^[4]
Monochromatic triangle^[2]Template:Rp
Pathwidth,^[5] or, equivalently, interval thickness, and vertex separation number^[6]
Rank coloring
k-Chinese postman
Shortest total path length spanning tree^[2]Template:Rp
Slope number two testing^[7]
Recognizing string graphs^[8]
Subgraph isomorphism problem^[2]Template:Rp
Treewidth^[5]
Testing whether a tree may be represented as Euclidean minimum spanning tree
Vertex cover^[1]^[2]Template:Rp

Mathematical programming

3-partition problem^[2]Template:Rp
Bin packing problem^[2]Template:Rp
Bottleneck traveling salesman^[2]Template:Rp
Uncapacitated facility location problem
Flow Shop Scheduling Problem
Generalized assignment problem
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^[1]^[2]Template:Rp
Some problems related to Job-shop scheduling
Knapsack problem, quadratic knapsack problem, and several variants^[1]^[2]Template:Rp
Some problems related to Multiprocessor scheduling
Numerical 3-dimensional matching^[2]Template:Rp
Open-shop scheduling
Partition problem^[1]^[2]Template:Rp
Quadratic assignment problem^[2]Template:Rp
Quadratic programming (NP-hard in some cases, P if convex)
Subset sum problem^[2]Template:Rp
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.^[2]Template:Rp

Formal languages and string processing

Closest string^[9]
Longest common subsequence problem over multiple sequences^[2]Template:Rp
The bounded variant of the Post correspondence problem^[2]Template:Rp
Shortest common supersequence over multiple sequences^[2]Template:Rp
Extension of the string-to-string correction problem^[10]^[2]Template:Rp

Games and puzzles

Bag (Corral)^[11]
Battleship
Bulls and Cows, marketed as Master Mind: certain optimisation problems but not the game itself.
Edge-matching puzzles
Fillomino^[12]
(Generalized) FreeCell^[13]
Goishi Hiroi
Hashiwokakero^[14]
Heyawake^[15]
(Generalized) Instant Insanity^[2]Template:Rp
Kakuro (Cross Sums)^[16]
Kingdomino^[17]
Kuromasu (also known as Kurodoko)^[18]
LaserTank^[19]
Lemmings (with a polynomial time limit)^[20]
Light Up^[21]
Mahjong solitaire (with looking below tiles)
Masyu^[22]
Minesweeper Consistency Problem^[23] (but see Scott, Stege, & van Rooij^[24])
Nonograms
Numberlink
Nurikabe^[25]
(Generalized) Pandemic^[26]
Peg solitaire
n-Queens completion
Optimal solution for the Template:Math Rubik's Cube^[27]
SameGame
Shakashaka
Slither Link on a variety of grids^[28]^[29]^[30]
(Generalized) Sudoku^[28]^[31]
Tatamibari
Tentai Show
Problems related to Tetris^[32]
Verbal arithmetic

Other

Berth allocation problem^[33]
Betweenness
Assembling an optimal Bitcoin block.^[34]
Boolean satisfiability problem (SAT).^[1]^[2]Template:Rp 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.^[2]Template:Rp
Circuit satisfiability problem
Conjunctive Boolean query^[2]Template:Rp
Cyclic ordering^[35]
Exact cover problem. Remains NP-complete for 3-sets. Solvable in polynomial time for 2-sets (this is a matching).^[1]^[2]Template:Rp
Finding the global minimum solution of a Hartree-Fock problem^[36]
Upward planarity testing^[7]
Hospitals-and-residents problem with couples
Knot genus^[37]
Latin square completion (the problem of determining if a partially filled square can be completed)
Maximum 2-satisfiability^[2]Template:Rp
Maximum volume submatrix – Problem of selecting the best conditioned subset of a larger $m \times n$ matrix. This class of problem is associated with Rank revealing QR factorizations and D optimal experimental design.^[38]
Minimal addition chains for sequences.^[39] The complexity of minimal addition chains for individual numbers is unknown.^[40]
Modal logic S5-Satisfiability
Pancake sorting distance problem for strings^[41]
Solubility of two-variable quadratic polynomials over the integers.^[42] Given positive integers $A, B, C$ , decide existence of positive integers $x, y$ such that $A x^{2} + B y - C = 0$
By the same article^[42] existence of bounded modular square roots with arbitrarily composite modulus. Given positive integers $A, B, C \geq 0$ , decide existence of an integer $x \in [0, C]$ such that $x^{2} \equiv A mod B$ . The problem remains NP-complete even if a prime factorization of $B$ is provided.
Serializability of database histories^[2]Template:Rp
Set cover (also called "minimum cover" problem). This is equivalent, by transposing the incidence matrix, to the hitting set problem.^[1]^[2]Template:Rp
Set packing^[1]^[2]Template:Rp
Set splitting problem^[2]Template:Rp
Scheduling to minimize weighted completion time
Block Sorting^[43] (Sorting by Block Moves)
Sparse approximation
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.^[2]Template:Rp
Three-dimensional Ising model^[44]

Notes

Template:Reflist

References

General

Template:Garey-Johnson. This book is a classic, developing the theory, then cataloguing many NP-Complete problems.
Script error: No such module "citation/CS1".
Script error: No such module "citation/CS1".
Script error: No such module "citation/CS1".
Script error: No such module "citation/CS1".
Script error: No such module "citation/CS1".

Specific problems

Script error: No such module "citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "citation/CS1".
Script error: No such module "citation/CS1".
Script error: No such module "Citation/CS1". Further information available online at Richard Kaye's Minesweeper pages.
Script error: No such module "citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "Citation/CS1".
Script error: No such module "citation/CS1".

External links

Template:Authority control

↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q Template:Harvtxt
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v ^w ^x ^y ^z ^aa ^ab ^ac ^ad ^ae ^af ^ag ^ah ^ai ^aj ^ak ^al ^am ^an ^ao ^ap ^aq ^ar ^as ^at ^au ^av ^aw ^ax ^ay ^az ^ba ^bb ^bc ^bd ^be Template:Harvtxt
↑ Minimum Independent Dominating Set
↑ Script error: No such module "citation/CS1".
↑ ^a ^b Template:Harvtxt
↑ Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.
↑ ^a ^b Script error: No such module "citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003.
↑ Script error: No such module "citation/CS1".
↑ Template:Harvtxt
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Light Up is NP-Complete
↑ Script error: No such module "citation/CS1".
↑ Template:Harvtxt
↑ Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, The Mathematical Intelligencer 33:4 (2011), pp. 5–17.
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ ^a ^b Script error: No such module "citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf)
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ J. Bonneau, "Bitcoin mining is NP-hard"
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "Citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981
↑ D. J. Bernstein, "Pippinger's exponentiation algorithm" (draft)
↑ Script error: No such module "Citation/CS1".
↑ ^a ^b Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

[karp-1] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q Template:Harvtxt

[gj1979-2] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l ^m ⁿ ^o ^p ^q ^r ^s ^t ^u ^v ^w ^x ^y ^z ^aa ^ab ^ac ^ad ^ae ^af ^ag ^ah ^ai ^aj ^ak ^al ^am ^an ^ao ^ap ^aq ^ar ^as ^at ^au ^av ^aw ^ax ^ay ^az ^ba ^bb ^bc ^bd ^be Template:Harvtxt

[3] Minimum Independent Dominating Set

[4] Script error: No such module "citation/CS1".

[acp1987-5] Template:Harvtxt

[6] Template:Harvtxt; Template:Harvtxt; Template:Harvtxt.

[Comp2Planar-7] Script error: No such module "citation/CS1".

[8] Script error: No such module "Citation/CS1".

[9] Script error: No such module "citation/CS1".

[10] Script error: No such module "citation/CS1".

[11] Script error: No such module "citation/CS1".

[12] Script error: No such module "citation/CS1".

[13] Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence 143(2):219-262, 2003.

[14] Script error: No such module "citation/CS1".

[Holzer-Ruepp07-15] Template:Harvtxt

[16] Script error: No such module "citation/CS1".

[17] Script error: No such module "Citation/CS1".

[Kölker12b-18] Script error: No such module "Citation/CS1".

[19] Script error: No such module "citation/CS1".

[Cormode04-20] Script error: No such module "citation/CS1".

[21] Light Up is NP-Complete

[Friedman-22] Script error: No such module "citation/CS1".

[23] Template:Harvtxt

[24] Allan Scott, Ulrike Stege, Iris van Rooij, Minesweeper may not be NP-complete but is hard nonetheless, The Mathematical Intelligencer 33:4 (2011), pp. 5–17.

[25] Script error: No such module "Citation/CS1".

[26] Script error: No such module "Citation/CS1".

[27] Script error: No such module "citation/CS1".

[sigal87-28] Script error: No such module "citation/CS1".

[NU07-29] Script error: No such module "Citation/CS1".

[Kölker12c-30] Script error: No such module "Citation/CS1".

[31] A SURVEY OF NP-COMPLETE PUZZLES, Section 23; Graham Kendall, Andrew Parkes, Kristian Spoerer; March 2008. (icga2008.pdf)

[32] Script error: No such module "citation/CS1".

[33] Script error: No such module "citation/CS1".

[34] J. Bonneau, "Bitcoin mining is NP-hard"

[35] Script error: No such module "Citation/CS1".

[36] Script error: No such module "Citation/CS1".

[37] Script error: No such module "citation/CS1".

[38] Script error: No such module "citation/CS1".

[39] Peter Downey, Benton Leong, and Ravi Sethi. "Computing Sequences with Addition Chains" SIAM J. Comput., 10(3), 638–646, 1981

[40] D. J. Bernstein, "Pippinger's exponentiation algorithm" (draft)

[41] Script error: No such module "Citation/CS1".

[NP-complete_decision_problems_for_Quadratic_Polynomials-42] Script error: No such module "citation/CS1".

[43] Script error: No such module "citation/CS1".

[44] Barry Arthur Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

List of NP-complete problems

Contents

Graphs and hypergraphs

Mathematical programming

Formal languages and string processing

Games and puzzles

Other

See also

Notes

References

External links

Navigation menu

List of NP-complete problems

Graphs and hypergraphs

Mathematical programming

Formal languages and string processing

Games and puzzles

Other

See also

Notes

References

External links

Navigation menu

Search