References

More reading on the 10 problems, and tools to help you climb. Start with Wikipedia. The papers and books below are the classic sources.

Background: P, NP and NP-completeness

Wikipedia: P versus NP problem, NP-completeness, Cook–Levin theorem.
Clay Mathematics Institute, P vs NP, one of the seven Millennium Prize Problems.
Stephen A. Cook, "The complexity of theorem-proving procedures", Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC '71), 1971, pp. 151–158. doi:10.1145/800157.805047
Richard M. Karp, "Reducibility among combinatorial problems", in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, 1972, pp. 85–103. doi:10.1007/978-1-4684-2001-2_9
Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, 1979. ISBN 0-7167-1045-5. The standard catalogue of NP-complete problems.
Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage Learning, 2013. ISBN 978-1-133-18779-0. Chapter 7 introduces P, NP and NP-completeness.
Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. doi:10.1017/CBO9780511804090

Boolean Satisfiability (SAT)

Wikipedia: Boolean satisfiability problem, SAT solver.
Classic: Cook 1971 (above), the first NP-completeness proof. For solving: Martin Davis and Hilary Putnam, "A computing procedure for quantification theory", Journal of the ACM 7(3), 1960, pp. 201–215, doi:10.1145/321033.321034; and Martin Davis, George Logemann and Donald Loveland, "A machine program for theorem-proving", Communications of the ACM 5(7), 1962, pp. 394–397, doi:10.1145/368273.368557 (DPLL, the method behind every modern solver).
Survey: Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsh (eds.), Handbook of Satisfiability, 2nd ed., IOS Press, 2021. doi:10.3233/FAIA336

3-SAT

Wikipedia: 3-satisfiability (a section of the SAT article).
Classic: Uwe Schöning, "A probabilistic algorithm for k-SAT and constraint satisfaction problems", 40th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 1999, pp. 410–414, doi:10.1109/SFFCS.1999.814612; journal version in Algorithmica 32(4), 2002, pp. 615–623, doi:10.1007/s00453-001-0094-7. A simple method that makes random moves. On 3-SAT it is faster than trying every case.
Textbook: Donald E. Knuth, The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, section 7.2.2.2 (Satisfiability). ISBN 0-201-03806-4.

Independent Set

Wikipedia: Independent set (graph theory).
Classic: Robert Endre Tarjan and Anthony E. Trojanowski, "Finding a maximum independent set", SIAM Journal on Computing 6(3), 1977, pp. 537–546. doi:10.1137/0206038
Textbook: Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010. doi:10.1007/978-3-642-16533-7

Clique

Wikipedia: Clique problem.
Classic: Coen Bron and Joep Kerbosch, "Algorithm 457: finding all cliques of an undirected graph", Communications of the ACM 16(9), 1973, pp. 575–577. doi:10.1145/362342.362367
Survey: Qinghua Wu and Jin-Kao Hao, "A review on algorithms for maximum clique problems", European Journal of Operational Research 242(3), 2015, pp. 693–709. doi:10.1016/j.ejor.2014.09.064

Vertex Cover

Wikipedia: Vertex cover.
Classic: G. L. Nemhauser and L. E. Trotter, "Vertex packings: structural properties and algorithms", Mathematical Programming 8(1), 1975, pp. 232–248. doi:10.1007/BF01580444 Also: Jianer Chen, Iyad A. Kanj and Ge Xia, "Improved upper bounds for vertex cover", Theoretical Computer Science 411(40–42), 2010, pp. 3736–3756. doi:10.1016/j.tcs.2010.06.026
Textbook: Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk and Saket Saurabh, Parameterized Algorithms, Springer, 2015. doi:10.1007/978-3-319-21275-3

Graph 3-Coloring

Wikipedia: Graph coloring.
Classic: Daniel Brélaz, "New methods to color the vertices of a graph", Communications of the ACM 22(4), 1979, pp. 251–256 (the DSatur method). doi:10.1145/359094.359101 Also: Richard Beigel and David Eppstein, "3-coloring in time O(1.3289^n)", Journal of Algorithms 54(2), 2005, pp. 168–204. doi:10.1016/j.jalgor.2004.06.008
Textbook: R. M. R. Lewis, Guide to Graph Colouring: Algorithms and Applications, 2nd ed., Springer, 2021. doi:10.1007/978-3-030-81054-2

Hamiltonian Cycle

Wikipedia: Hamiltonian path problem, Hamiltonian path.
Classic: Michael Held and Richard M. Karp, "A dynamic programming approach to sequencing problems", Journal of the Society for Industrial and Applied Mathematics 10(1), 1962, pp. 196–210, doi:10.1137/0110015; and Richard Bellman, "Dynamic programming treatment of the travelling salesman problem", Journal of the ACM 9(1), 1962, pp. 61–63, doi:10.1145/321105.321111. Modern: Andreas Björklund, "Determinant sums for undirected Hamiltonicity", SIAM Journal on Computing 43(1), 2014, pp. 280–299. doi:10.1137/110839229
Survey: Ronald J. Gould, "Advances on the Hamiltonian problem – a survey", Graphs and Combinatorics 19(1), 2003, pp. 7–52. doi:10.1007/s00373-002-0492-x
Hard instances: Joeri Sleegers and Daan van den Berg, "The hardest Hamiltonian cycle problem instances: the plateau of yes and the cliff of no", SN Computer Science 3, article 372, 2022. Open access. doi:10.1007/s42979-022-01256-0

Travelling Salesperson (TSP)

Wikipedia: Travelling salesman problem.
Classic: G. Dantzig, R. Fulkerson and S. Johnson, "Solution of a large-scale traveling-salesman problem", Journal of the Operations Research Society of America 2(4), 1954, pp. 393–410, doi:10.1287/opre.2.4.393; and S. Lin and B. W. Kernighan, "An effective heuristic algorithm for the traveling-salesman problem", Operations Research 21(2), 1973, pp. 498–516, doi:10.1287/opre.21.2.498. Held and Karp 1962 (above) is the classic exact dynamic program.
Book: David L. Applegate, Robert E. Bixby, Vašek Chvátal and William J. Cook, The Traveling Salesman Problem: A Computational Study, Princeton University Press, 2006. ISBN 978-0-691-12993-8.

0-1 Integer Programming

Wikipedia: Integer programming, Pseudo-Boolean function.
Classic: Karp 1972 (above) lists 0-1 integer programming among its 21 NP-complete problems. For solving: Ralph E. Gomory, "Outline of an algorithm for integer solutions to linear programs", Bulletin of the American Mathematical Society 64(5), 1958, pp. 275–278, doi:10.1090/S0002-9904-1958-10224-4 (cutting planes); and Egon Balas, "An additive algorithm for solving linear programs with zero-one variables", Operations Research 13(4), 1965, pp. 517–546, doi:10.1287/opre.13.4.517 (branch and bound on 0-1 variables).
Textbook: Laurence A. Wolsey, Integer Programming, 2nd ed., Wiley, 2020. doi:10.1002/9781119606475 Also: Michele Conforti, Gérard Cornuéjols and Giacomo Zambelli, Integer Programming, Springer, 2014. doi:10.1007/978-3-319-11008-0
The file format: Olivier Roussel and Vasco Manquinho, Input/Output Format and Solver Requirements for the Competitions of Pseudo-Boolean Solvers (the OPB format), 2016. The Pseudo-Boolean Competition 2024 has results, solvers and benchmarks.

Exact Cover by 3-Sets (X3C)

Wikipedia: Exact cover (exact cover by 3-sets is the case where every set has three elements), Knuth's Algorithm X, Dancing links.
Classic: Donald E. Knuth, "Dancing links", in Millennial Perspectives in Computer Science, 2000, pp. 187–214. arXiv:cs/0011047 The problem appears as [SP2] in Garey and Johnson 1979 (above).
Textbook: Donald E. Knuth, The Art of Computer Programming, Volume 4B, Addison-Wesley, 2023, section 7.2.2.1 (Dancing links). ISBN 0-201-03806-4.

Solvers and tools

Each licence is as the project states it. "Academic use" means other uses may need permission.

SAT

Kissat (Armin Biere and others; source). MIT.
CaDiCaL (Armin Biere and others; source). MIT.
MiniSat (source). MIT. Described in Niklas Eén and Niklas Sörensson, "An extensible SAT-solver", Theory and Applications of Satisfiability Testing (SAT 2003), LNCS 2919, Springer, 2004, pp. 502–518, doi:10.1007/978-3-540-24605-3_37.
CryptoMiniSat (source). MIT for everything needed to build and run it. Some extra files are GPLv2.
The International SAT Competition: yearly results, solver sources and benchmark sets.
Handbook of Satisfiability (see SAT).

Graphs (independent set, clique, vertex cover)

KaMIS: maximum independent sets and vertex covers of large sparse graphs. MIT.
Cliquer (Patric Östergård and others): exact maximum and maximum-weight clique search. GNU GPL.
PMC (Ryan A. Rossi): parallel maximum clique. GNU GPL v3 or later.
NetworkX (source): Python graph library for small experiments. BSD 3-clause.

Exact cover

Donald E. Knuth's DLX1, Algorithm 7.2.2.1X (exact cover by dancing links), in CWEB. Neither the program nor the page that lists it states a licence.

Travelling salesperson and Hamiltonian cycle

Concorde (Applegate, Bixby, Chvátal, Cook): exact symmetric TSP solver. Academic research use is allowed. Other uses need a licence from William Cook.
LKH and LKH-3 (Keld Helsgaun): the Lin–Kernighan–Helsgaun method for finding short tours, not always the shortest. LKH also solves Hamiltonian cycle problems directly. For academic and non-commercial use only. The author reserves all rights.

General constraint and integer programming solvers

RoundingSat (Jan Elffers, Jakob Nordström and others): pseudo-Boolean solver that reads OPB files. MIT. Described in Jan Elffers and Jakob Nordström, "Divide and conquer: towards faster pseudo-Boolean solving", Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI-18), 2018, pp. 1291–1299, doi:10.24963/ijcai.2018/180.
OR-Tools CP-SAT (Google; source). Apache 2.0.
SCIP (source): constraint integer programming; reads OPB files. Apache 2.0.
HiGHS (source): linear and mixed-integer programming. MIT.