# 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[citation needed] 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.

## Graph theory

### Covering and partitioning

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.
This is the same problem as coloring the complement of the given graph.[6]
NP-complete special cases include the minimum maximal matching problem,[13] which is essentially equal to the edge dominating set problem (see above).

## Network design

### Graph Drawing

Graphs occur frequently in everyday applications, and are used to model a lot of often huge data. Such examples include biological or social networks, which contain hundreds, thousands and even billions of nodes in some cases (see e.g. Facebook or LinkedIn). Therefore, even when all information is available in the form of a graph, it is important to have good ways of visualizing the data in order to make sense of it and extract interesting features, and this is what makes graph drawing important.

## Sequencing and scheduling

### Sequencing on one processor

• Job sequencing[1]
• 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

## Logic

### Propositional logic

Propositional logic problems, in particular satisfiability problems and their variants, are of particular practical interest because many practical problems can be solved by expressing them as satisfiability problems, and then using efficient SAT solvers to obtain an exact solution quickly[citation needed].

## Computational geometry

• 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)[149]
• 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.[150]
• Art gallery problem and its variations.

## Notes

1. ^ Garey & Johnson (1979): GT1
2. ^ Garey & Johnson (1979): GT2
3. ^ Garey & Johnson (1979): GT3
4. ^ Garey & Johnson (1979): GT4
5. ^ Garey & Johnson (1979): GT15
6. ^ Garey & Johnson (1979): GT5
7. ^ Garey & Johnson (1979): GT6
8. ^ Garey & Johnson (1979): GT7
9. ^ Garey & Johnson (1979): GT8
10. ^ Garey & Johnson (1979): GT9
11. ^ Minimum Independent Dominating Set
12. ^ Garey & Johnson (1979): GT10
13. ^ Garey & Johnson (1979): GT11
14. ^ Garey & Johnson (1979): GT12
15. ^ Garey & Johnson (1979): GT13
16. ^ Garey & Johnson (1979): GT14
17. ^ Garey & Johnson (1979): GT16
18. ^ Garey & Johnson (1979): GT17
19. ^ Garey & Johnson (1979): GT18
20. ^ a b Garey & Johnson (1979): GT56
21. ^ a b
22. ^ Garey & Johnson (1979): GT19
23. ^ Garey & Johnson (1979): GT20
24. ^ Garey & Johnson (1979): GT23
25. ^ Garey & Johnson (1979): GT24
26. ^ Garey & Johnson (1979): GT25
27. ^ Garey & Johnson (1979): GT26
28. ^ Garey & Johnson (1979): GT27
29. ^ Garey & Johnson (1979): GT28
30. ^ Garey & Johnson (1979): GT29
31. ^ Garey & Johnson (1979): GT30
32. ^ Garey & Johnson (1979): GT31
33. ^ Garey & Johnson (1979): GT32
34. ^ Garey & Johnson (1979): GT33
35. ^ Garey & Johnson (1979): GT34
36. ^ Garey & Johnson (1979): GT35
37. ^ Garey & Johnson (1979): GT36
38. ^ Garey & Johnson (1979): GT37
39. ^ Garey & Johnson (1979): GT38
40. ^ Garey & Johnson (1979): GT39
41. ^ Garey & Johnson (1979): GT40
42. ^ Garey & Johnson (1979): GT41
43. ^ Garey & Johnson (1979): GT42
44. ^ Garey & Johnson (1979): GT43
45. ^ Garey & Johnson (1979): GT44
46. ^ Garey & Johnson (1979): GT45
47. ^ Garey & Johnson (1979): GT46
48. ^ Garey & Johnson (1979): GT47
49. ^
50. ^ Garey & Johnson (1979): GT48
51. ^ Garey & Johnson (1979): GT49
52. ^ Garey & Johnson (1979): GT50
53. ^ Garey & Johnson (1979): GT51
54. ^ Garey & Johnson (1979): GT52
55. ^ Garey & Johnson (1979): GT53
56. ^ Garey & Johnson (1979): GT54
57. ^ Garey & Johnson (1979): GT55
58. ^ Garey & Johnson (1979): GT57
59. ^ Garey & Johnson (1979): GT58
60. ^ Garey & Johnson (1979): GT59
61. ^ Garey & Johnson (1979): GT60
62. ^ Garey & Johnson (1979): GT61
63. ^ Garey & Johnson (1979): GT62
64. ^ Garey & Johnson (1979): GT63
65. ^ Garey & Johnson (1979): GT64
66. ^ Garey & Johnson (1979): GT65
67. ^ "Normalized Cuts and Image Segmentation". IEEE. 20 October 2009.
68. ^ a b "On the computational complexity of upward and rectilinear planarity testing". Lecture Notes in Computer Science. 894/1995. 1995. pp. 286–297. doi:10.1007/3-540-58950-3_384.
69. ^ Garey & Johnson (1979): SP1
70. ^ Garey & Johnson (1979): SP2
71. ^ Garey & Johnson (1979): SP3
72. ^ Garey & Johnson (1979): SP4
73. ^ Garey & Johnson (1979): SP5
74. ^ Garey & Johnson (1979): SP6
75. ^ Garey & Johnson (1979): SP7
76. ^ Garey & Johnson (1979): SP8
77. ^ Garey & Johnson (1979): SP9
78. ^ Garey & Johnson (1979): SP10
79. ^ Garey & Johnson (1979): SP11
80. ^ Garey & Johnson (1979): SR1
81. ^ Garey & Johnson (1979): SR2
82. ^ Garey & Johnson (1979): SR3
83. ^ Garey & Johnson (1979): SR4
84. ^ Garey & Johnson (1979): SR5
85. ^ Garey & Johnson (1979): SR6
86. ^ Garey & Johnson (1979): SR7
87. ^ Garey & Johnson (1979): SR8
88. ^ Garey & Johnson (1979): SR9
89. ^ Garey & Johnson (1979): SR10
90. ^ Garey & Johnson (1979): SR11
91. ^ Garey & Johnson (1979): SR12
92. ^ Garey & Johnson (1979): SR13
93. ^ Garey & Johnson (1979): SR14
94. ^ Garey & Johnson (1979): SR15
95. ^ Garey & Johnson (1979): SR16
96. ^ Garey & Johnson (1979): SR17
97. ^ Garey & Johnson (1979): SR18
98. ^ Garey & Johnson (1979): SR19
99. ^ Garey & Johnson (1979): SR20
100. ^ Garey & Johnson (1979): SR21
101. ^ Garey & Johnson (1979): SR22
102. ^ Garey & Johnson (1979): SR23
103. ^ Garey & Johnson (1979): SR24
104. ^ Garey & Johnson (1979): SR25
105. ^ Garey & Johnson (1979): SR26
106. ^ Garey & Johnson (1979): SR27
107. ^ Garey & Johnson (1979): SR28
108. ^ Garey & Johnson (1979): SR29
109. ^ Garey & Johnson (1979): SR30
110. ^ Garey & Johnson (1979): SR31
111. ^ Garey & Johnson (1979): SR32
112. ^ Garey & Johnson (1979): SR33
113. ^ Garey & Johnson (1979): SR34
114. ^ Garey & Johnson (1979): SR35
115. ^ Garey & Johnson (1979): SR36
116. ^ http://www.cs.rpi.edu/~civria/max-vol-inapprox.pdf
117. ^ Yato, Takauki (2003). "Complexity and Completeness of Finding Another Solution and its Application to Puzzles". CiteSeerX: 10.1.1.103.8380.
118. ^ R. Clifford, M. Jalsenius, A. Montanaro and B. Sach (2010-08-19). The Complexity of Flood Filling Games. arXiv:1001.4420.
119. ^ Malte Helmert, Complexity results for standard benchmark domains in planning, Artificial Intelligence Journal 143(2):219-262, 2003.
120. ^
121. ^ Kölker, Jonas (2012). Kurodoko is NP-complete.
122. ^ Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs".
123. ^ Kölker, Jonas (2012). The Magnets puzzle is NP-Complete.
124. ^ Friedman, Erich (2012-03-27). "Pearl Puzzles are NP-complete".
125. ^
126. ^ 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.
127. ^ Yato; Seta. Complexity and Completeness of Finding Another Solution and Its Application to Puzzles.
128. ^
129. ^ Nukui; Uejima. ASP-Completeness of the Slither Link Puzzle on Several Grids.
130. ^ Kölker, Jonas (2012). Selected Slither Link Variants are NP-complete.
131. ^ G. Aloupis, E. D. Demaine, A. Guo (2012-03-09). "Classic Nintendo Games are (NP-)Hard".
132. ^ Garey & Johnson (1979): LO1
133. ^ Garey & Johnson (1979): LO2
134. ^ Garey & Johnson (1979): LO3
135. ^ Garey & Johnson (1979): LO4
136. ^ Garey & Johnson (1979): LO5
137. ^ Garey & Johnson (1979): LO6
138. ^ Garey & Johnson (1979): LO8
139. ^ Garey & Johnson (1979): LO9
140. ^ Garey & Johnson (1979): LO10
141. ^ Garey & Johnson (1979): AL7
142. ^ Garey & Johnson (1979): AL8
143. ^ Garey & Johnson (1979): AL10
144. ^ Garey & Johnson (1979): AL11
145. ^ Garey & Johnson (1979): AL15
146. ^ Garey & Johnson (1979): AL17
147. ^ Garey & Johnson (1979): AL18
148. ^ H. Breu and David G. Kirkpatrick. "Unit Disk Graph Recognition is NP-hard." Comput. Geom. Theory Appl., 9(1-2):3–24, 1998
149. ^ "Assembly Into Two Connected Parts Is NP-Complete", Inf. Proc. Letters 55 (1995), 159-165.
150. ^ Barry A. Cipra, "The Ising Model Is NP-Complete", SIAM News, Vol 33, No 6.

## References

• Holzer, Markus; Ruepp, Oliver (2007). "The Troubles of Interior Design–A Complexity Analysis of the Game Heyawake". Proceedings, 4th International Conference on Fun with Algorithms, LNCS 4475. Springer, Berlin/Heidelberg. pp. 198–212. doi:10.1007/978-3-540-72914-3_18. ISBN 978-3-540-72913-6.
• Cormode, Graham (2004). "The hardness of the lemmings game, or Oh no, more NP-completeness proofs". Proceedings of Third International Conference on Fun with Algorithms (FUN 2004). pp. 65–76.