Karp's 21 NP-complete problems

In

Karp's 21 problems are shown below, many with their original names. The nesting indicates the direction of the reductions used. For example, Knapsack was shown to be NP-complete by reducing Exact cover to Knapsack.

• Satisfiability: the boolean satisfiability problem for formulas in conjunctive normal form (often referred to as SAT)
  • 0–1 integer programming
    (A variation in which only the restrictions must be satisfied, with no optimization)
  • independent set problem
    )
    • Set packing
    • Vertex cover
      • Set covering
      • Feedback node set
      • Feedback arc set
      • Directed Hamilton circuit (Karp's name, now usually called Directed Hamiltonian cycle)
        • Undirected Hamilton circuit (Karp's name, now usually called Undirected Hamiltonian cycle)
  • Satisfiability with at most 3 literals per clause (equivalent to 3-SAT)
    • Chromatic number (also called the Graph Coloring Problem)
      • Clique cover
      • Exact cover
        • Hitting set
        • Steiner tree
        • 3-dimensional matching
        • Subset sum
          )
          • Job sequencing
          • Partition
            • Max cut