Karp's 21 NP-complete Problems - The Problems

The Problems

Karp's 21 problems, many with their original names, are shown below, with the nesting indicating 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
  • CLIQUE (see also 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 CIRCUIT)
        • UNDIRECTED HAMILTON CIRCUIT (Karp's name, now usually called UNDIRECTED HAMILTONIAN CIRCUIT)
  • 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
        • KNAPSACK (Karp's definition of Knapsack is closer to Subset sum)
          • JOB SEQUENCING
          • PARTITION
            • MAX CUT

As time went on it was discovered that many of the problems can be solved efficiently if restricted to special cases, or can be solved within any fixed percentage of the optimal result. However, David Zuckerman showed in 1996 that every one of these 21 problems has a constrained optimization version that is impossible to approximate within any constant factor unless P = NP, by showing that Karp's approach to reduction generalizes to a specific type of approximability reduction. Note however that these may be different from the standard optimization versions of the problems, which may have approximation algorithms (as in the case of maximum cut).