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.
- Minimum weight triangulation for a set of points in the plane [1]
- 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)[2]
- 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 A\S by a collision-free rigid motion of S, and such that both S and A\S are connected. [3]
Graph theory
Covering and partitioning
Vertex cover · Dominating set · Domatic number · Graph k-colorability · Achromatic 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 · 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 · 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
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
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
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 · Consucutive 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
Database problems
Minimum cardinality key · Additional key · Prime attribute name · Boyce-Codd normal form violation · Conjunctive query foldability · Conjunctive boolean 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 · Comparative vector inequalities
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 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
Games and puzzles
Generalized hex · Generalized geography · Generalized Kayles · Sequential truth assignment · Variable partition truth assignment · Sift · Alternating hitting set · Alternating maximum weighted matching · Annihilation · Left-right Hackenbush for Redwood furniture · Square-tiling · Crossword puzzle construction · Generalized instant insanity · Minesweeper Consistency Problem · Sudoku · Nurikabe · Paint by numbers · Light Up · Slither Link . Cross Sums · Clickomania · Tetris · Mastermind . Masyu
Logic
Propositional logic
Satisfiability · 3-Satisfiability · Not-all-equal 3SAT · One-in-three 3SAT · Maximum 3-Satisfiability · Generalized satisfiability · Satisfiability of boolean expressions · Non-tautology · Minimum disjunctive normal form · Truth-functionally complete connectives
Miscellaneous
Quantified boolean formulas · First order theory of equality · Modal logic S5-Satisfiability · Modal logic provability · Predicate logic without negation · Conjunctive satisfiability with functions and inequalities · Minimum axiom set · First order subsumption · Second order instantiation
Automata and language theory
Automata theory
Finite state automaton inequivalence · Two-way finite state automaton non-emptiness · Linear bounded automaton acceptance · Quasi-realtime automaton acceptance · Non-erasing stack automaton acceptance · Finite state automata intersection · Reduction of incompletely specified automata · Minimum inferred finite state automaton
Formal languages
Regular expression inequivalence · 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 · Context-sensitive 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
References
- ^ Minimum Weight Triangulation is NP-Hard, 22nd SCG (2006)
- ^ H. Breu and D. G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3--24, 1998
- ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
- M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman. 1983. ISBN 0-7167-1045-5.
- Erich Friedman. "Pearl Puzzles are NP-Complete". In preparation. 2002. [1].
- Paul E. Dunne. An Annotated List of Selected NP-complete Problems. The University of Liverpool, Dept of Computer Science, COMP202.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, and Gerhard Woeginger. A compendium of NP optimization problems. KTH NADA. Stockholm.