List of NP-complete problems

Here are some of the more commonly known problems that are NP-complete when expressed as decision problems. This list is in no way comprehensive (there are more than 3000 known NP-complete problems). Most of the problems in this list are taken from Garey and Johnson's seminal book "Computers and Intractability: A Guide to the Theory of NP-Completeness", and are here presented in the same order and organization.

Computational geometry

*Minimum weight triangulation for a set of points in the plane [ [http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cs/0601002 Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)] ]
*Testing whether a tree may be represented as Euclidean minimum spanning tree
*Unit disk graph recognition (Unit disk graphs are intersection graphs of circles of unit radius in the plane) [H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998]
*Many motion planning among polygonal obstacles in the plane are NP-hard.
**Planar partitioning into connected subassemblies: Given a set A of non-overlapping (but possibly touching) polygons in the plane, decide if there is a proper subset S of A that can be separated from AS by a collision-free rigid motion of S, and such that both S and AS are connected. ["Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165. ]

Graph theory

Covering and partitioning

*Vertex cover
*Dominating set
*Domatic number
*Graph k-colorability
*Achromatic number
*Grundy number
*Monochromatic triangle
*Feedback vertex set
*Feedback arc set
*Partial feedback edge set
*Minimum maximal matching
*Partition into triangles
*Partition into isomorphic subgraphs
*Partition into Hamiltonian subgraphs
*Partition into forests
*Partition into cliques
*Partition into perfect matchings
*Two-stage maximum weight stochastic matching
*Covering by cliques
*Berth Allocation Problem (BAP)
*Covering by complete bipartite subgraphs

Subgraphs and supergraphs

*Clique
*Independent set
*Induced subgraph with property Pi
*Induced connected subgraph with property Pi
*Induced path
*Balanced complete bipartite subgraph
*Bipartite subgraph
*Degree-bounded connected subgraph
*Planar subgraph
*Edge-subgraph
*Transitive subgraph
*Uniconnected subgraph
*Minimum k-connected subgraph
*Cubic subgraph
*Minimum equivalent digraph
*Hamiltonian completion
*Interval graph completion
*Path graph completion

Vertex ordering

*Hamiltonian circuit
*Directed Hamiltonian circuit
*Hamiltonian path
*Bandwidth
*Directed bandwidth
*Optimal linear arrangement
*Directed optimal linear arrangement
*Minimum cut linear arrangement
*Rooted tree arrangement
*Directed elimination ordering
*Elimination degree sequence

Iso- and other morphisms

*Subgraph isomorphism
*Largest common subgraph
*Maximum subgraph matching
*Graph contractability
*Graph homomorphism
*Digraph D-morphism

Miscellaneous

*Path with forbidden pairs
*Multiple choice matching
*Graph Grundy numbering
*Kernel
*K-closure
*Intersection graph basis
*Path distinguishers
*Metric dimension
*Nesetril-Rödl dimension
*Threshold number
*Oriented diameter
*Weighted diameter

Network design

Spanning trees

*Degree-constrained spanning tree
*Minimum degree spanning tree
*Maximum leaf spanning tree
*Shortest total path length spanning tree
*Bounded diameter spanning tree
*Capacitated spanning tree
*Geometric capacitated spanning tree
*Optimum communication spanning tree
*Isomorphic spanning tree
*Kth best spanning tree
*Bounded component spanning forest
*Multiple choice branching
*Steiner tree
*Geometric Steiner tree
*Cable Trench Problem
*Minimum Touching Tree/Minimum Length Corridor

Cuts and connectivity

*Graph partitioning
*Acyclic partition
*Max weight cut
*Minimum cut into bounded sets
*Biconnectivity augmentation
*Strong connectivity augmentation
*Network reliability
*Network survivability
*Multiway Cut
*Minimum k-cut

Routing problems

*Bottleneck traveling salesman
*Chinese postman for mixed graphs
*Euclidean traveling salesman
*K most vital arcs
*Kth shortest path
*Metric traveling salesman
*Longest circuit
*Longest path
*Prize Collecting Traveling Salesman
*Rural Postman
*Shortest path in general networks
*Shortest weight-constrained path
*Stacker-crane
*Time constrained traveling salesman feasibility
*Traveling salesman problem
*Vehicle routing problem

Flow problems

*Minimum edge-cost flow
*Integral flow with multipliers
*Path constrained network flow
*Integral flow with homologous arcs
*Integral flow with bundles
*Undirected flow with lower bounds
*Directed two-commodity integral flow
*Undirected two-commodity integral flow
*Disjoint connecting paths
*Maximum length-bounded disjoint paths
*Maximum fixed-length disjoint paths
*Unsplittable multicommodity flow

Miscellaneous

*Quadratic assignment problem
*Minimizing dummy activities in PERT networks
*Constrained triangulation
*Intersection graph for segments on a grid
*Edge embedding on a grid
*Geometric connected dominating set
*Minimum broadcast time
*Min-max multicenter
*Min-sum multicenter
*Uncapacitated Facility Location
*Metric k-center

Sets and partitions

Covering, hitting, and splitting

*3-dimensional matching
*Exact cover
*Set packing
*Set splitting
*Set cover
*Minimum test set
*Set basis
*Hitting set
*Intersection pattern
*Comparative containment
*3-matroid intersection

Weighted set problems

*Partition
*Subset sum
*Subset product
*3-partition
*Numerical 3-dimensional matching
*Numerical matching with target sums
*Expected component sum
*Minimum sum of squares
*Kth largest subset
*Kth largest m-tuple

Set partitions

*Median partition

Storage and retrieval

Data storage

*Bin packing
*Dynamic storage allocation
*Pruned trie space minimization
*Expected retrieval cost
*Rooted tree storage assignment
*Multiple copy file allocation
*Capacity assignment

Compression and representation

*Shortest common supersequence
*Shortest common superstring
*Longest common subsequence problem for the case of arbitrary (i.e., not "a priori" fixed) number of input sequences even in the case of the binary alphabet
*Bounded post correspondence problem
*Hitting string
*Sparse matrix compression
*Consecutive ones submatrix
*Consecutive ones matrix partition
*Consecutive ones matrix augmentation
*Consecutive block minimization
*Consecutive sets
*2-dimensional consecutive sets
*String-to-string correction
*Grouping by swapping
*External macro data compression
*Internal macro data compression
*Regular expression substitution
*Rectilinear picture compression
*Optimal vector quantization codebook
*Minimal grammar-based compression
*Adaptive Block-size Compression

Database problems

*Minimum cardinality key
*Additional key
*Prime attribute name
*Boyce-Codd normal form violation
*Conjunctive query foldability
*Boolean conjunctive query
*Tableau equivalence
*Serializability of database histories
*Safety of database transaction systems
*Consistency of database frequency tables
*Safety of file protection systems

Sequencing and scheduling

Sequencing on one processor

*Sequencing with release times and deadlines
*Sequencing to minimize Tardy tasks
*Sequencing to minimize Tardy weight
*Sequencing to minimize weighted completion time
*Sequencing to minimize weighted tardiness
*Sequencing with deadlines and set-up times
*Sequencing to minimize maximum cumulative cost

Multiprocessor scheduling

*Multiprocessor scheduling
*Precedence constrained scheduling
*Resource constrained scheduling
*Scheduling with individual deadlines
*Preemptive scheduling
*Scheduling to minimize weighted completion time

Shop scheduling

*Open-shop scheduling
*Flow-shop scheduling
*No-wait flow-shop scheduling
*Two-processor flow-shop with bounded buffer
*Job-shop scheduling

Miscellaneous

*Timetable design
*Staff scheduling
*Production planning
*Deadlock avoidance

Mathematical programming

Integer programming
*0-1 Integer programming
*Quadratic programming (NP-hard in some cases, P when convex)
*Cost-parametric linear programming
*Feasible basis extension
*Minimum weight solution to linear equations
*Open hemisphere
*K-relevancy
*Traveling salesman polytope non-adjacency
*Knapsack
*Integer knapsack
*Continuous multiple choice knapsack
*Partially ordered knapsack
*Generalized assignment problem
*Comparative vector inequalities
*Sparse approximation

Algebra and number theory

Divisibility problems

*Quadratic congruences
*Simultaneous incongruences
*Simultaneous divisibility of linear polynomials
*Comparative divisibility
*Exponential expression divisibility
*Non-divisibility of a product polynomial
*Non-trivial greatest common divisor

Solvability of equations

*Quadratic diophantine equations
* [Algebraic equations over GF2|Algebraic equations over GF [2] ]
*Root of modulus 1
*Number of roots for a product polynomial
*Periodic solution recurrence relation

Miscellaneous

*Permanent evaluation
*Cosine product integration
*Equilibrium point
*Unification with commutative operators
*Unification for finitely presented algebras
*Integer expression membership
*Minimal addition chain

Games and puzzles

Alternating hitting set
*Alternating maximum weighted matching
*Annihilation
*Battleship
*Clickomania (SameGame)
*Cross Sums
*Crossword puzzle construction
*FreeCell
*Instant Insanity
*Light Up
*LITS
*Mastermind
*Masyu
*Minesweeper Consistency Problem
*Nurikabe
*Paint by numbers (Nonogram)
*Rabin games
*Sift
*Slither Link
*Square-tiling
*Sudoku
*Tetris
*Variable partition truth assignment
*Verbal arithmetic

Logic

Propositional logic

*Satisfiability
*3-Satisfiability
*Not-all-equal 3SAT
*One-in-three 3SAT
*Maximum 3-Satisfiability
*Generalized satisfiability
*Non-tautology
*Minimum disjunctive normal form
*Truth-functionally complete connectives
*Planar-3SAT
*Monotone-3SAT

Miscellaneous

*Modal logic S5-Satisfiability
*Negation-free logic
*Conjunctive satisfiability with functions and inequalities
*Minimum axiom set
*First order subsumption
*Second order instantiation

Automata and language theory

Automata theory

*Two-way finite state automaton non-emptiness
*Quasi-realtime automaton acceptance
*Reduction of incompletely specified automata
*Minimum inferred finite state automaton

Formal languages

*Minimum inferred regular expression
*Reynolds covering for context-free grammars
*Covering for linear grammars
*Structural inequivalence for linear grammars
*Regular grammar inequivalence
*Non-LR(K) context-free grammar
*Etol grammar non-emptiness
*Context-free programmed language membership
*Quasi-real-time language membership
*Etol language membership
*Tree transducer language membership

Program optimization

Code generation

*Register sufficiency
*Feasible register assignment
*Register sufficiency for loops
*Code generation on a one-register machine
*Code generation with unlimited registers
*Code generation for parallel assignments
*Code generation with address expressions
*Code generation with unfixed variable locations
*Ensemble computation
*Microcode bit optimization

Programs and schemes

*Inequivalence of programs with arrays
*Inequivalence of programs with assignments
*Inequivalence of finite memory programs
*Inequivalence of loop programs without nesting
*Inequivalence of simple functions
*Strong inequivalence of Ianov schemes
*Strong inequivalence for monadic recursion
*Non-containment for free B-schemes
*Non-freedom for loop-free program schemes
*Programs with formally recursive procedures

Miscellaneous

*Cyclic ordering
*Non-liveness of free choice Petri nets
*Reachability for 1-conservative Petri nets
*Finite function generation
*Permutation generation
*Decoding of linear codes
*Shapley-Shubik voting power
*Clustering
*Randomization test for matched pairs
*Maximum likelihood ranking
*Matrix domination
*Matrix cover
*Simply deviated disjunction
*Decision tree
*Minimum weight and/or graph solution
*Fault detection in logic circuits
*Fault detection in directed graphs
*Fault detection with test points

See also

* Karp's 21 NP-complete problems
* List of PSPACE-complete problems

References

* cite book
last = Garey
first = M.R.
authorlink = Michael Garey
coauthors = Johnson, D.S.
title =
year = 1979
publisher = W.H. Freeman
location = New York
isbn = 0-7167-1045-5 This book is a classic, developing the theory, then cataloguing "many" NP-Complete problems.
* cite conference
last = Cook
first = S.A.
authorlink = Stephen A. Cook
title = The complexity of theorem proving procedures
booktitle = Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York
year = 1971
pages = 151–158
url = http://dx.doi.org/10.1145/800157.805047
doi = 10.1145/800157.805047
* cite web
last = Dunne
first = P.E
title = An annotated list of selected NP-complete problems
publisher = COMP202, Dept. of Computer Science, University of Liverpool
url = http://www.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html
accessdate = 2008-06-21
* cite web
last = Crescenzi
first = P.
coauthors = Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G
title = A compendium of NP optimization problems
publisher = KTH NADA, Stockholm
url = http://www.nada.kth.se/~viggo/problemlist/compendium.html
accessdate = 2008-06-21
* cite web
last = Dahlke
first = K
title = NP-complete problems
work = Math Reference Project
url = http://www.mathreference.com/lan-cx-np,intro.html
accessdate = 2008-06-21
* cite web
first = E
last = Friedman
title = Pearl puzzles are NP-complete
year = 2002
publisher = Stetson University, DeLand, Florida
url = http://www.stetson.edu/~efriedma/papers/pearl/pearl.html
accessdate = 2008-06-21