Classic Papers - Reducibility Among Combinatorial Problems

Richard Karp’s 1972 paper “Reducibility Among Combinatorial Problems” crystallised NP-completeness as a unifying lens for hard problems. Building on Cook’s theorem, Karp showed how to shuttle hardness across domains by giving polynomial-time many-one reductions from SAT to 21 natural problems (e.g., Clique, Vertex Cover, Hamiltonian Cycle, Set Cover).

Reduction Construction

Karp constructed explicit polynomial-time mappings $x \mapsto f(x)$ from SAT as a known NP-complete problem to 21 combinatorial problems, such that:

$$x \in \text{SAT} \iff f(x) \in \text{TARGET}$$

where $f$ is computable in polynomial time. By chaining such reductions, each target problem inherits NP-hardness. The paper established a foundational network of reductions that remains canonical in complexity theory.

Theoretical Significance

• Complexity Classification: Membership in NP-complete indicates the necessity of approximation algorithms, heuristics, parameterised approaches, or exploitation of special structure rather than general polynomial-time algorithms.
• Structural Correspondence: Reductions reveal deep connections between disparate domains (graph theory, satisfiability, combinatorial optimization), enabling cross-pollination of algorithmic techniques and lower bound methods.
• Methodological Framework: The work established the standard proof technique for hardness results: construct a polynomial-time reduction from a known NP-complete problem through carefully designed gadgets that preserve solution structure.

Contemporary Applications

Karp’s reduction methodology remains fundamental to modern complexity theory:

• Establishing hardness of new problem variants and domain-specific formulations through systematic reduction construction.
• Developing inapproximability results via gap-preserving reductions and fine-grained complexity lower bounds based on ETH/SETH hypotheses.
• Informing practical constraint encoding strategies where reduction insights guide SAT/ILP formulation design and solver integration.

Reduction in Practice: Scheduling Encodings

Consider a job scheduling problem with machine conflicts, time windows, and precedence constraints. Contemporary SAT/SMT/ILP encodings employ reduction techniques analogous to Karp’s constructions:

1. Add Boolean variables $x_{j,t}$ meaning “job $j$ starts at time $t$.”
2. Enforce single-start: for each job, forbid two distinct start times with clauses $\lnot x_{j,t} \lor \lnot x_{j,t'}$ for $t \neq t'$.
3. Enforce machine capacity: for each machine and overlapping times, add clauses that block two jobs from occupying the machine simultaneously.
4. Encode precedence: if $a$ precedes $b$, require $b$‘s start to be after $a$ finishes via implication clauses or linear constraints.

The resulting SAT instance inherits NP-hardness from classical scheduling through standard reductions, while providing access to efficient solver implementations. This exemplifies Karp’s methodological contribution: reduction constructions serve dual purposes as hardness proofs and practical encoding frameworks.

The 21 problems in Karp’s original work established that diverse combinatorial problems form equivalence classes under polynomial reduction. This classification guides algorithmic strategy: exact methods for tractable cases, approximation schemes for hard problems with structure, and constraint solver approaches where general intractability applies.