whoashish's cp notes

🐬 References

11 min read

The sources these notes are built on and cross-checked against. Learning material (courses, problem sets, contests) is in Resources.

Primary references

  1. cp-algorithms — https://cp-algorithms.com — algorithm articles with proofs and code
  2. KACTL (KTH Algorithm Competition Template Library) — https://github.com/kth-competitive-programming/kactl — tested ICPC notebook
  3. OI Wiki — https://oi-wiki.org — the most complete Chinese OI reference
  4. USACO Guide — https://usaco.guide — topic-ordered curriculum with problems
  5. AtCoder Library (ACL) — https://github.com/atcoder/ac-library — reference implementations
  6. Antti Laaksonen, Competitive Programmer’s Handbook — https://cses.fi/book/book.pdf
  7. Antti Laaksonen, Guide to Competitive Programming (Springer)
  8. Steven & Felix Halim, Competitive Programming 4 — https://cpbook.net
  9. Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS)
  10. Kleinberg & Tardos, Algorithm Design — greedy, flows, NP-completeness chapters
  11. Codeforces EDU and blogs — https://codeforces.com/edu/courses
  12. CSES Problem Set — https://cses.fi/problemset
  13. Shahjalal Shohag, A List of Useful Equations in Competitive Programming — https://shahjalalshohag.com/blog/equation-list/ (style of Formula)
  14. cp-template — https://github.com/whoashish115/cp-template — the implementations linked from Templates

NP-Hard Books

1. Garey & Johnson’s NP-Complete Problems (The classic list)

The book Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson categorizes hundreds of NP-complete problems.

2. Karp’s 21 NP-Complete Problems

Richard M. Karp proved the first 21 NP-complete problems and grouped them into categories such as:

3. Complexity Zoo

The Complexity Zoo is an online encyclopedia of complexity classes.

There is no complete list of all computational problems—new problems are defined all the time. However, there are canonical lists of the most studied problems. Here’s a comprehensive categorization.

1. Tractable Problems (P)

Sorting

  • Comparison Sorting
  • Counting Sort
  • Radix Sort
  • Bucket Sort

Searching

  • Binary Search
  • Dictionary Lookup
  • Order Statistics
  • Range Search

Graph

  • BFS
  • DFS
  • Shortest Path
  • All-Pairs Shortest Path
  • Minimum Spanning Tree
  • Topological Sort
  • SCC
  • Bridge Finding
  • Articulation Points
  • Euler Tour
  • Maximum Flow
  • Minimum Cost Flow
  • Bipartite Matching
  • General Matching

String

  • Pattern Matching
  • KMP
  • Z Algorithm
  • Rabin-Karp
  • Suffix Array
  • Suffix Automaton
  • Trie
  • Aho-Corasick

Geometry

  • Convex Hull
  • Closest Pair
  • Line Sweep
  • Half Plane Intersection

Number Theory

  • GCD
  • Extended GCD
  • Modular Exponentiation
  • Miller-Rabin
  • Pollard Rho
  • CRT

Algebra

  • Gaussian Elimination
  • Matrix Multiplication
  • FFT
  • NTT

Optimization

  • Linear Programming
  • Assignment Problem
  • Transportation Problem

2. NP Problems

  • SAT
  • 2-SAT
  • 3-SAT
  • Hamiltonian Path
  • Hamiltonian Cycle
  • Traveling Salesman (Decision)
  • Clique
  • Vertex Cover
  • Independent Set
  • Set Cover
  • Exact Cover
  • Subset Sum
  • Partition
  • Bin Packing
  • Knapsack (Decision)
  • Dominating Set
  • Longest Path
  • Steiner Tree
  • Graph Coloring
  • Facility Location
  • Hitting Set

3. NP-Complete Problems

Logic
  • SAT
  • 3-SAT
  • Circuit SAT
Graph
  • Clique
  • Independent Set
  • Vertex Cover
  • Hamiltonian Cycle
  • Hamiltonian Path
  • Graph Coloring
  • Dominating Set
  • Feedback Vertex Set
  • Feedback Arc Set
  • Longest Path
  • Steiner Tree
  • Edge Dominating Set
Set
  • Set Cover
  • Exact Cover
  • Hitting Set
  • Exact Hitting Set
  • Set Splitting
Number
  • Subset Sum
  • Partition
  • Knapsack
  • Integer Programming (Decision)
Geometry
  • Euclidean TSP (Decision)
  • Rectilinear Steiner Tree
Scheduling
  • Job Shop Scheduling
  • Open Shop Scheduling
  • Flow Shop Scheduling
  • Nurse Scheduling
  • Timetabling
Packing
  • Bin Packing
  • Strip Packing
  • Cutting Stock
Games
  • Sudoku
  • Kakuro
  • Nonogram
  • Minesweeper Consistency

4. NP-Hard Problems

  • Traveling Salesman (Optimization)
  • Maximum Clique
  • Maximum Independent Set
  • Minimum Vertex Cover
  • Chromatic Number
  • Minimum Dominating Set
  • Minimum Set Cover
  • Minimum Steiner Tree
  • Vehicle Routing
  • Capacitated Vehicle Routing
  • Quadratic Assignment
  • General Integer Programming
  • Mixed Integer Programming
  • Circuit Minimization
  • Boolean Formula Minimization
  • Protein Folding
  • Genome Assembly (optimization variants)
  • Sparse PCA
  • Tensor Rank
  • Bayesian Network Learning
  • Optimal Decision Tree
  • Symbolic Regression
  • Register Allocation
  • Frequency Assignment

5. PSPACE-Complete

  • Quantified Boolean Formula (QBF)
  • Generalized Geography
  • Generalized Hex
  • Generalized Reversi
  • Generalized Sokoban
  • Rush Hour
  • Constraint Logic
  • LTL Model Checking
  • CTL Model Checking

6. EXPTIME-Complete

  • Generalized Chess
  • Generalized Checkers
  • Generalized Go
  • Infinite-Horizon Games
  • Alternating Turing Machine Acceptance

7. Undecidable Problems

  • Halting Problem
  • Busy Beaver
  • Post Correspondence Problem
  • Program Equivalence
  • Rice’s Theorem Problems
  • First-Order Logic Validity
  • Hilbert’s Tenth Problem
  • Word Problem for Semigroups
  • Mortality Problem

Classic “Must-Know” Problems (about 30)

If you’re interested in algorithms or theoretical computer science, these are the core problems almost everyone studies:

Polynomial-Time (P)
  • Sorting
  • Binary Search
  • Shortest Path
  • Minimum Spanning Tree
  • Maximum Flow
  • Bipartite Matching
  • Linear Programming
  • FFT
  • String Matching
  • Convex Hull
NP-Complete / NP-Hard
  • SAT
  • 3-SAT
  • Traveling Salesman
  • Clique
  • Vertex Cover
  • Independent Set
  • Hamiltonian Cycle
  • Graph Coloring
  • Set Cover
  • Exact Cover
  • Knapsack
  • Subset Sum
  • Partition
  • Dominating Set
  • Steiner Tree
  • Longest Path
  • Feedback Vertex Set
  • Bin Packing
  • Job Shop Scheduling
  • Vehicle Routing

These problems serve as the standard reference points for reductions and complexity analysis in computer science.

NP-hard / NP-complete Resource Catalog

This is a large reference list, not a mathematically complete enumeration. The number of known NP-hard / NP-complete problems is enormous and keeps growing through new variants and reductions.

Best starting resources

  • Garey & Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness
  • Karp’s 21 NP-complete problems
  • Complexity Zoo
  • Wikipedia: List of NP-complete problems
  • GitHub repo: graphofnpcompletereductions/graphofnpcompletereductions.github.io
  • GitHub repo: CodingThrust/problem-reductions
  • GitHub repo: lawliet89/np-complete

GitHub / online resources

Books and surveys

  • Garey & Johnson — Computers and Intractability
  • Papadimitriou — Computational Complexity
  • Sipser — Introduction to the Theory of Computation
  • Arora & Barak — Computational Complexity: A Modern Approach
  • Vazirani — Approximation Algorithms
  • Crescenzi & Kann — A Compendium of NP Optimization Problems
  • Hammer, Johnson, Korte — works on combinatorial optimization
  • Surveys on NP-complete puzzles and NP-complete reductions

Canonical NP-complete / NP-hard problems

Logic and satisfiability
  • SAT
  • 3-SAT
  • 1-in-3 SAT
  • Exact 3-SAT
  • Circuit SAT
  • NAE-SAT
  • Horn-SAT variants
  • Max-SAT
  • Weighted Max-SAT
  • Boolean formula minimization
  • Boolean formula equivalence (various forms)
  • Quantified Boolean Formula (QBF)
  • True quantified Boolean formula
  • Boolean circuit minimization
  • Boolean circuit satisfiability
Set and subset problems
  • Subset Sum
  • Partition
  • 3-Partition
  • Equal Sum Partition
  • Minimum Set Cover
  • Set Cover
  • Hitting Set
  • Exact Cover
  • Exact Cover by 3-Sets
  • Set Packing
  • Set Splitting
  • Maximum Coverage
  • Minimum Set Splitting
  • Minimum Hitting Set
  • k-Set Packing
  • Minimum Union Cover
  • Minimum Test Set
Graph theory problems
  • Clique
  • Maximum Clique
  • Independent Set
  • Maximum Independent Set
  • Vertex Cover
  • Minimum Vertex Cover
  • Dominating Set
  • Minimum Dominating Set
  • Total Dominating Set
  • Connected Dominating Set
  • k-Dominating Set
  • Clique Cover
  • Chromatic Number
  • Graph Coloring
  • k-Colorability
  • Edge Coloring (general variants)
  • Hamiltonian Cycle
  • Hamiltonian Path
  • Traveling Salesman (decision)
  • Traveling Salesman (optimization)
  • Steiner Tree
  • Steiner Forest
  • Minimum Steiner Tree
  • Feedback Vertex Set
  • Minimum Feedback Vertex Set
  • Feedback Arc Set
  • Minimum Feedback Arc Set
  • Cutwidth
  • Bandwidth
  • Minimum Linear Arrangement
  • Minimum Bisection
  • Max Cut
  • Min Cut variants with constraints
  • Treewidth
  • Pathwidth
  • Branchwidth
  • Graph Isomorphism variants
  • Subgraph Isomorphism
  • Induced Subgraph Isomorphism
  • Clique Cover
  • Edge Dominating Set
  • Total Clique Cover
  • Minimum Fill-In
  • Chordal Completion
  • Planarity variants
  • Upward Planarity
  • 1-Planarity
  • Crossing Number
  • Two-layer crossing minimization
  • Graph embedding variants
  • Minimum Spanning Tree variants with constraints
  • Capacitated MST
  • Degree-constrained spanning tree
  • k-Tree variants
  • Maximum Acyclic Subgraph
  • Minimum Equivalent Digraph
  • Longest Path
  • Shortest Hamiltonian path variants
  • Disjoint Paths
  • k-Disjoint Paths
  • Graph Motif
  • Directed Feedback Set
  • Minimum DFS tree variants
  • Power domination variants
  • Rainbow connection variants
  • Domatic Number
  • k-Coloring of line graphs variants
  • Clique Partition
  • Maximum Cut with constraints
  • Minimum Dominating Edge Set
  • Minimum Connected Vertex Cover
  • Minimum k-Vertex Cover
  • Minimum k-Edge Cover with constraints
  • Graph Partition into Cliques
  • Graph Partition into Paths
  • Graph Partition into Forests
  • Perfect Code
  • Efficient Dominating Set
Matching and allocation
  • General Matching (optimization variants)
  • Maximum Weight Matching variants
  • Stable Marriage with couples
  • Hospitals and Residents with couples
  • Assignment problems with side constraints
  • Generalized Assignment Problem
  • Generalized Matching with capacities
  • B-matching variants
  • Minimum Cost Perfect Matching variants with constraints
  • Task assignment variants
Scheduling and sequencing
  • Job Shop Scheduling
  • Open Shop Scheduling
  • Flow Shop Scheduling
  • Machine Scheduling with deadlines
  • Multiprocessor Scheduling
  • Nurse Scheduling
  • Timetabling
  • Course Timetabling
  • University Exam Timetabling
  • Project Scheduling with resource constraints
  • Weighted Completion Time Scheduling
  • Makespan Minimization variants
  • Release-date scheduling variants
  • Precedence-constrained scheduling variants
  • Batch Scheduling variants
  • Parallel Machine Scheduling variants
  • Interval Scheduling with conflicts
  • Sequencing with setup times
  • Task allocation with precedence
  • Berth Allocation
  • Airport Gate Assignment
  • Crew Scheduling
Packing and covering
  • Bin Packing
  • Bin Packing with conflicts
  • Strip Packing
  • Two-dimensional packing
  • Three-dimensional packing
  • Cutting Stock
  • Knapsack
  • Multiple Knapsack
  • Quadratic Knapsack
  • Partition into triangles
  • Rectangle packing
  • Circle packing variants
  • Shelf packing variants
  • Resource allocation with packing constraints
Routing and logistics
  • Vehicle Routing Problem
  • Capacitated Vehicle Routing Problem
  • Traveling Repairman Problem
  • Rural Postman Problem
  • Chinese Postman variants on mixed graphs
  • Orienteering Problem
  • Prize-Collecting TSP
  • Bottleneck TSP
  • Steiner Traveling Salesman variants
  • Facility Location
  • Uncapacitated Facility Location
  • Capacitated Facility Location
  • p-Median
  • p-Center
  • k-Center
  • k-Median
  • Hub Location Problem
  • Location-Routing Problem
Geometry and spatial optimization
  • Euclidean TSP
  • Rectilinear TSP
  • Rectilinear Steiner Tree
  • Euclidean Steiner Tree
  • Geometric Set Cover
  • Point Cover by Disks
  • Segment Intersection problems with constraints
  • Minimum enclosing variants with combinatorial constraints
  • Maximum independent set in geometric intersection graphs
  • Packing circles / squares / rectangles variants
  • Geometric hitting set variants
  • Geometric dominating set variants
  • Visibility graph problems
  • Art gallery variants
  • Guard placement
  • Motion planning variants
String and language problems
  • Closest String
  • Closest Substring
  • Longest Common Subsequence over multiple sequences
  • Shortest Common Supersequence over multiple sequences
  • Post Correspondence Problem (bounded variant)
  • String-to-string correction variants
  • Multiple sequence alignment variants
  • Consensus string variants
  • DNA mapping variants
  • Sequence assembly variants
  • Regular expression equivalence variants
  • Grammar-based minimization variants
  • Edit distance variants with many sequences
Algebra, number theory, and arithmetic
  • Integer Programming
  • 0-1 Integer Programming
  • Mixed Integer Programming
  • Quadratic Programming (nonconvex)
  • Quadratic Assignment Problem
  • Sparse PCA
  • Tensor Rank
  • Matrix completion variants with combinatorial constraints
  • Minimum rank problem
  • Boolean matrix factorization
  • Linear ordering problem
  • Exact factorization variants
  • Subset product variants
  • Number partitioning variants
  • Coin change variants with constraints
  • Modular subset problems
  • Simultaneous Diophantine approximation variants
Data mining and learning
  • Optimal decision tree
  • Minimum decision tree size
  • Bayesian network structure learning
  • Sparse feature selection with hard constraints
  • Rule list minimization
  • Boolean function learning variants
  • Sparse regression with subset constraints
  • Clustering with combinatorial constraints
  • Facility location learning variants
  • Minimum description length optimization variants
Games and puzzles
  • Sudoku
  • Kakuro
  • Nonogram
  • Minesweeper consistency
  • Minesweeper solving variants
  • Slither Link
  • Hashiwokakero
  • Heyawake
  • Nurikabe
  • Masyu
  • Fillomino
  • Battleship puzzle
  • Numberlink
  • Shakashaka
  • Tatamibari
  • Tentai Show
  • Light Up / Akari
  • LITS
  • Corral / Bag puzzle
  • FreeCell (generalized)
  • Peg solitaire
  • Rubik’s Cube optimal solving
  • SameGame
  • Tetris-related optimization
  • Mastermind optimization variants
  • Sokoban
  • Generalized Sokoban
  • Rush Hour
  • Generalized Rush Hour
  • Generalized Chess
  • Generalized Checkers
  • Generalized Go
  • Generalized Hex
  • Generalized Geography
  • Hex variants
  • Reversi / Othello variants
  • Lemmings variants
  • Tetris
  • Clickomania
  • Blocks / box puzzles
  • Sliding puzzles with obstacles
  • Edge-matching puzzles
  • Instant Insanity
  • n-Queens completion
Computational biology / chemistry / physics
  • Protein folding
  • RNA secondary structure with constraints
  • Genome assembly variants
  • Haplotyping variants
  • Phylogeny reconstruction variants
  • Maximum parsimony variants
  • Molecular docking variants
  • Hartree-Fock global optimization
  • Ising model optimization variants
  • Spin glass optimization
  • VLSI layout variants
  • Circuit layout
  • Wire routing
  • Floorplanning
  • Physical design partitioning
Miscellaneous classic NP-hard problems
  • Minimum Latency Problem
  • Traveling Tournament Problem
  • Maximum Common Subgraph
  • Maximum Common Induced Subgraph
  • Graph Motif
  • Minimum Clique Cover
  • Partition into induced subgraphs
  • Minimum chain decomposition variants
  • Feedback Vertex Set in tournaments
  • Minimum filler problems
  • Minimum completion problems
  • Correlation clustering
  • Cluster editing
  • Cluster deletion
  • Split graph completion
  • Threshold graph editing
  • Perfect graph recognition variants
  • Database query minimization variants
  • View selection with constraints
  • Broadcast scheduling variants
  • Network design with survivability constraints
  • Survivable network design
  • Steiner forest with demands
  • Directed Steiner tree
  • Group Steiner tree
  • Prize-collecting Steiner tree
  • Maximum weight induced forest
  • Minimum cycle cover with constraints

Karp’s 21 problems

  • SAT
  • 3-SAT
  • CLIQUE
  • VERTEX COVER
  • INDEPENDENT SET
  • HAMILTONIAN CYCLE
  • HAMILTONIAN PATH
  • TSP decision
  • SET COVER
  • EXACT COVER
  • HITTING SET
  • PARTITION
  • SUBSET SUM
  • KNAPSACK
  • 3-DIMENSIONAL MATCHING
  • DOMINATING SET
  • GRAPH COLORING
  • CHROMATIC NUMBER
  • CLIQUE COVER
  • FEEDBACK VERTEX SET
  • FEEDBACK ARC SET
  • STEINER TREE

Notes on terminology

  • NP-hard means at least as hard as every problem in NP under polynomial reductions.
  • NP-complete means NP-hard and also in NP.
  • Many optimization versions are NP-hard even when the decision version is NP-complete.
  • Many puzzles are NP-complete only in generalized form.

Suggested study path

  1. Learn the definition of P, NP, NP-hard, and NP-complete.
  2. Study Karp’s 21 problems.
  3. Read Garey & Johnson.
  4. Use the reduction graph and compendium links.
  5. Practice reductions from SAT, 3-SAT, CLIQUE, VERTEX COVER, and SET COVER.

Papers

Read original work when a proof, condition, or specialist algorithm exceeds a short contest note.

For each paper extract: problem model, assumptions, theorem statement, invariant, complexity model, and implementation gap. A faster asymptotic theorem may have constants or machinery unsuitable for a contest notebook. Specialist reading should follow strong coverage of standard graph, DP, string, geometry, and arithmetic techniques.

Record the exact version and a counterexample to any assumption you remove. Avoid replacing a proof with an algorithm’s name.

Graph View