Reducibility among Combinatorial Problems
Complexity of Computer Computations, 1972 · paper · Computer science
Karp recounts the background to his work on reducing combinatorial problems to one another, following Cook's 1971 result on satisfiability. The text shown covers only the introduction and does not state the paper's results.
Checked: PDF from cs.umd.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
11 findings
Substance Main Theorem items 7 and 8 (p.94) omit the size bound. They print 'PROPERTY: There is a set R ⊆ V such that every (directed) cycle of H contains a node in R' and '...a set S ⊆ E such that every (directed) cycle of H contains an arc in S', and the input k is never used (|R| ≤ k, |S| ≤ k are missing).
- p. 14 Main Theorem list, item 7
There is a set R ⊆ V such that every (directed) cycle of H contains a node in R.
- p. 14 Problem 8 FEEDBACK ARC SET
There is a set S ⊆ E such that every (directed) cycle of H contains an arc in S.
Judge's note: The p.14 image confirms that neither property mentions k, whereas NODE COVER (item 5) states '|R| ≤ ℓ'. As printed, R = V or S = E always works, so every instance is a yes-instance. The reductions on p.98 set k = ℓ, which presupposes the bound. Checked the counterexample: G' with a single edge and ℓ = 0 is a no-instance of NODE COVER, but it maps to H with arcs <1,2>,<2,1>, and R = {1,2} meets the cycle.
Second check: another model agreed
Report a problem with this finding
Substance 0-1 INTEGER PROGRAMMING is defined with 'There exists a 0-1 vector x such that Cx = d' (p.94), but the reduction SATISFIABILITY ∝ 0-1 INTEGER PROGRAMMING (p.97: c_ij = 1/−1/0, 'b_i = 1 − (the number of complemented variables in C_i)') captures clause satisfaction only as Cx ≥ b. With equality it requires exactly one true literal per clause.
- p. 14 Main Theorem list, item 2
There exists a 0-1 vector x such that Cx = d.
- p. 17 SATISFIABILITY ∝ 0-1 INTEGER PROGRAMMING
b_i = 1 - (the number of complemented variables in C_i)
- p. 14 Main Theorem, problem 2
PROPERTY: There exists a 0-1 vector x such that Cx = d.
Only the authors can say what is right here.
Judge's note: Reworked the step on the p.17 image: row i equals (#true literals in C_i) − (#complemented variables in C_i), so row i ≥ b_i iff C_i has at least one true literal, and = b_i iff exactly one does. Counterexample: C1 = {x1,x2}, C2 = {x1,x̄2}, which is satisfiable with x1 = 1. The rows are x1+x2 = 1 and x1−x2 = 0. Checking all four 0-1 vectors: (0,0) gives row 1 = 0; (1,0) gives row 2 = 1; (0,1) gives row 2 = −1; (1,1) gives row 1 = 2. None is feasible. So the reduction as printed maps a yes-instance to a no-instance. The right-hand side is also named b in the reduction but d in the problem statement (see C008).
Second check: another model agreed
Report a problem with this finding
Substance EXACT COVER ∝ STEINER TREE as printed (R = {n_0} ∪ {u_i}, w({n_0,S_j}) = |S_j|, "w({S_j,u_i}) = 0", k = |{u_i}|) maps some no-instances to yes-instances, because zero-weight arcs let a tree reach a set node through an element node.
- p. 19 Reduction EXACT COVER ∝ STEINER TREE
w({S_j,u_i}) = 0
- p. 15 Problem 16 STEINER TREE
G has a subtree of weight ≤ k containing the set of nodes in R.
Only the authors can say what is right here.
Judge's note: Page 19 image confirms the construction. Page 15, problem 16: undirected graph G, R ⊆ N, w: A → Z, and the property is a subtree of weight ≤ k containing R. My check of the counterexample: elements u1, u2, u3 with S1={u1,u2} and S2={u2,u3}. There is no exact cover, since neither set alone covers and the two overlap at u2. The tree with arcs n0–S1 (weight 2), S1–u1, S1–u2, u2–S2, S2–u3 (weight 0 each) has 6 nodes and 5 arcs, is connected and contains R. Its weight is 2 ≤ k = 3, so the Steiner instance is a yes-instance while the exact cover instance is a no-instance. The reduction as printed is invalid.
Second check: another model agreed
Report a problem with this finding
Substance SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE ∝ CHROMATIC NUMBER (p.99) sets 'k = r+1', where r is the number of clauses D_1..D_r. The construction needs m+1 colours, where m is the number of variables.
- p. 19 SATISFIABILITY WITH AT MOST 3 LITERALS PER CLAUSE ∝ CHROMATIC NUMBER
k = r+1
Only the authors can say what is right here.
Judge's note: Reworked from the p.19 image. {v_i,v_j} for all i≠j makes v_1..v_m a clique, so at least m colours are needed. With m colours plus one extra 'false' colour the construction works as intended. Appendix I (p.23) and item 11 define D_1..D_r as clauses and u_1..u_m as variables. Checked counterexample: m = 4, r = 1, D_1 = {u_1} is satisfiable, but k = 2 colours cannot colour the K4 on v_1..v_4. With k = m+1 the result stands, but the printed formula is wrong.
Second check: another model agreed
Report a problem with this finding
Substance In SAT3 ∝ CHROMATIC NUMBER the arc set ends "∪ {{u_i,D_f}| u_i ∉ D_f} ∪ {{ū_i,D_f}| ū_i ∈ D_f}"; the second condition prints ∈ where ∉ is required for the construction to work.
- p. 19 Reduction SAT3 ∝ CHROMATIC NUMBER, arc set A
∪ {{u_i,D_f}| u_i ∉ D_f} ∪ {{ū_i,D_f}| ū_i ∈ D_f}
- p. 19 edge set A in the chromatic number reduction
ū_i ∈ D_f
Only the authors can say what is right here.
Judge's note: In the page 19 image the first term has the slashed ∉ glyph and the second has an unslashed ∈. My reworking: for the reduction to work, D_f must be adjacent to every literal it does not contain, so that its colour equals the colour of a true literal in the clause. With ∈, D_f is adjacent to the complemented literals it does contain and not to those it lacks. I checked the reviewer's counterexample: m=4, D1={u1}, D2={ū1}, which is unsatisfiable. Colour v_i with i. Give u1 colour 1, ū1 colour 5, ū2 colour 2, u2 colour 5, u3 colour 3, ū3 colour 5, u4 colour 4, ū4 colour 5. Under the printed rule, D1 is adjacent to u2, u3, u4 (colours 5, 3, 4), so colour 1 works. D2 is adjacent to u1..u4 and ū1 (colours 1, 5, 3, 4, 5), so colour 2 works. Every v-to-literal arc with i≠j is proper. The printed condition is therefore wrong. (Separately, the page prints k = r+1, which is not part of this cluster.)
Second check: another model agreed
Report a problem with this finding
Substance PARTITION ∝ MAX CUT sets "W = ⌈¼ Σ c_i²⌉" (sum of squares); with w({i,j}) = c_i·c_j on the complete graph the threshold must be ⌈¼(Σc_i)²⌉.
- p. 20 PARTITION ∝ MAX CUT
W = ⌈¼ Σ c_i²⌉
- p. 20 Reduction PARTITION ∝ MAX CUT
W = ⌈1/4 Σ c_i^2⌉
Only the authors can say what is right here.
Judge's note: In the page 20 image the exponent 2 sits on c_i inside the sum, with no parentheses around the sum. Problem 21 (page 17) asks for a cut weight ≥ W. The cut weight of S is (Σ_S c)(Σ_{not S} c). This is at most (Σc)²/4, with equality iff the two sides balance. My counterexample: c=(1,2), which has no partition. The printed W is ⌈5/4⌉ = 2, and the cut {1} has weight 2 ≥ 2, so the MAX CUT instance is yes. With (Σc)²/4 = 2.25, W would be 3 and the instance would correctly be no.
Second check: another model agreed
Report a problem with this finding
Substance In SAT3 ∝ EQUIVALENCE OF REGULAR EXPRESSIONS the first expression is "Δ^nΔ*" and the second is "Δ^nΔ* ∪ ∪_{i=1}^n (Δ*u_iΔ*ū_iΔ* ∪ Δ*ū_iΔ*u_iΔ*) ∪ ∪_h θ(D_h)"; for every formula with n ≥ 3 the string u_1ū_1 lies in the second but not the first, so the map is constant and cannot be a reduction.
- p. 21 Reduction SAT3 ∝ EQUIVALENCE OF REGULAR EXPRESSIONS
The first regular expression is Δ^nΔ*
- p. 21 second regular expression
Δ^nΔ* ∪ ∪_{i=1}^n (Δ*u_iΔ*ū_iΔ* ∪ Δ*ū_iΔ*u_iΔ*) ∪ ∪_{h=1}^r θ(D_h)
- p. 22 definition of θ(D_h)
Δ*σ̄_1Δ* if D_h = σ_1
Only the authors can say what is right here.
Judge's note: Page 21 image: the text defines Δ^n explicitly as 'n copies of the expression for Δ concatenated together', so Δ^nΔ* is the set of strings of length ≥ n. The second expression always contains Δ*u_1Δ*ū_1Δ*, which includes u_1ū_1, of length 2. For n ≥ 3 that string is not in Δ^nΔ*, so the two expressions are inequivalent whatever the clauses θ(D_h) (page 22) are. A satisfiable instance and an unsatisfiable instance on 3 variables therefore get the same answer. My own reworking confirms that the construction as printed does not give the claimed reduction.
Second check: another model agreed
Report a problem with this finding
Wording Proof of Theorem 1 (p.92): 'a machine which first guesses the successive digits of a string y of length ≤ p(lg(y))', where the bound should be in terms of the input, p(lg(x)).
- p. 12 Proof of Theorem 1 (⇒ direction), first lines
of length ≤ p(lg(y))
- p. 12 Proof of Theorem 1, ⇒ direction
of length ≤ p(lg(y)) and then tests whether <x,y> ∈ L^(2)
Only the authors can say what is right here.
Judge's note: The p.12 image shows 'p(lg(y))'. p-bounded existential quantification (p.90–91) requires lg(y) ≤ p(lg(x)), and the converse direction on the same page uses lg(y) ≤ p(lg(x)). A bound on y in terms of its own length is vacuous and gives no polynomial bound on the guessing phase. With p(lg(x)) the step works, so Theorem 1 stands.
Second check: another model agreed
Report a problem with this finding
Wording In SAT3 ∝ CHROMATIC NUMBER the arc set A begins "{{u_i,ū_i}| i=1,2,...,n}" although the variables and nodes are indexed u_1..u_m ("Assume without loss of generality that m ≥ 4"); n is undefined here and should be m.
- p. 19 3-SAT ∝ CHROMATIC NUMBER, definition of A
Assume without loss of generality that m ≥ 4.
- p. 17 3-SAT ∝ CHROMATIC NUMBER, definition of A
i=1,2,...,n
Judge's note: Page 19 image: the node set runs to m, and 'm ≥ 4' is assumed, but the first arc set runs i=1,2,...,n. Problem 11 (page 15) and Appendix I (page 23) index the 3-SAT variables by m; n is the variable count only for plain SATISFIABILITY. The page 17 quote 'i=1,2,...,n' belongs to the SATISFIABILITY/CLIQUE reductions and is correct there. Cluster C016 covers the x_j part of reviewer note 1.
Second check: another model agreed
Report a problem with this finding
Wording NODE COVER ∝ DIRECTED HAMILTON CIRCUIT (p.98) uses 'V = {a_1,a_2,...,a_ℓ} ∪ {<u,i,α>| ...}' with no restriction on ℓ. When ℓ exceeds the number of non-isolated nodes, no Hamilton circuit exists even though a cover of size ≤ ℓ does.
- p. 18 Reduction NODE COVER ∝ DIRECTED HAMILTON CIRCUIT
V = {a_1,a_2,...,a_ℓ} ∪ {<u,i,α>| u ∈ N' is incident with i ∈ A'
Only the authors can say what is right here.
Judge's note: Reworked from the p.18 image. Arcs out of a_f go only to <u,i,0> where i is the first arc incident with u, so there is one such target per non-isolated node. In a Hamilton circuit each node has a single predecessor, so the number of selectors ℓ is at most the number of non-isolated nodes. Checked counterexample: a single edge {1,2} with ℓ = 3 has the cover {1,2}, but a_1, a_2, a_3 have only the two targets <1,1,0> and <2,1,0>. Capping ℓ repairs the reduction, so the result stands; the paper states no such assumption.
Second check: another model agreed
Report a problem with this finding
Wording In SAT3 ∝ CHROMATIC NUMBER the arc set A contains "{{v_i,x_j}| i≠j} ∪ {{v_i,x̄_j}| i≠j}", but the node set N has only u_j, ū_j, v_j and D_f; x_j/x̄_j are not nodes of this graph (the fix is evidently u_j, ū_j).
- p. 19 3-SAT ∝ CHROMATIC NUMBER, arc set A
{{v_i,x_j}| i≠j}
Judge's note: Page 19 image: N = {u_1..u_m} ∪ {ū_1..ū_m} ∪ {v_1..v_m} ∪ {D_1..D_r}, and A contains {{v_i,x_j}| i≠j} and {{v_i,x̄_j}| i≠j}. Appendix I (page 23) uses x_1..x_n for SATISFIABILITY and u_1..u_m for the 3-literal problem (problem 11, page 15). So x_j is not defined in this construction. The intended u_j/ū_j is clear from context, so I classed this as a notation slip.
Second check: another model agreed
Report a problem with this finding
9 minor (typos and the like; most checked by the judge only)
Reference or label The attribution paragraph cites "Cook (1971) showed that SATISFIABILITY ∝ ..." and then "is implicit in Cook (1970)"; every other citation of Cook in the article is 1971, and no reference list identifies a 1970 work.
- p. 20 Attribution paragraph, p.100
is implicit in Cook (1970), and was also known to Raymond Reiter.
- p. 20 Attribution paragraph, p.100
Cook (1971) showed that SATISFIABILITY
- p. 2 References of retrospective introduction
S.A. Cook, The complexity of theorem proving procedures, Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, 1971
Only the authors can say what is right here.
Judge's note: Page 20 image shows both 'Cook (1971)' and 'Cook (1970)' in the same paragraph. A grep of the text finds Cook cited as 1971 everywhere else (lines 162, 389, 509 and 893). The only Cook entry in the files is the 1971 STOC paper, listed in the retrospective introduction's references. The reprinted article has no reference list (see C024), so it cannot be settled here whether a separate 1970 Cook work is meant. That is a query for the authors.
Second check: another model agreed
Report a problem with this finding
Reference or label The reprinted article ("pp. 85–103") cites by author–year (e.g. "MINIMUM CUT [Edmonds & Karp (1972)]", Salomaa (1969), Hopcroft & Ullman (1969), Cook (1970/1971)), but its last page (p.103) is APPENDIX I and there is no reference list to resolve the citations.
- p. 23 Last page of article (p.103), Appendix I
APPENDIX I
- p. 4 Reprint note
Plenum Press, 1972, pp. 85– 103.
- p. 10 Section 2 problem list
MINIMUM CUT [Edmonds & Karp (1972)]
Judge's note: Page 23 (p.103) holds Appendix I with blank space below and no references. Pages 19–22 contain only reductions and problem lists. The only reference list in the files is the one-item list of the retrospective introduction on page 2. Within the files the author–year citations cannot be resolved. Whether the original 1972 printing had a reference list cannot be checked here, so I treat this as an observation about the reprinted document.
Second check: another model agreed
Report a problem with this finding
Wording The 2010 introduction says of the undirected Hamilton circuit problem 'that reduction was provided independently by Lawler and Tarjan', but the article (p.101) credits Tarjan and Lawler independently with reductions to DIRECTED HAMILTON CIRCUIT and says 'DIRECTED HAMILTON CIRCUIT ∝ UNDIRECTED HAMILTON CIRCUIT was pointed out by Tarjan.'
- p. 2 Introduction by Karp, first paragraph
that re-duction was provided independently by Lawler and Tarjan
- p. 21 Attribution paragraph
DIRECTED HAMILTON CIRCUIT ∝ UNDIRECTED HAMILTON CIRCUIT
- p. 2 Introduction by Richard M. Karp, para 1
I failed to prove the NP-completeness of the undirected hamiltonian circuit problem; that re- duction was provided independently by Lawler and Tarjan
- p. 21 Attribution of reductions, top of p.101
and, independently, Lawler showed that
Only the authors can say what is right here.
Judge's note: Checked p.2 (intro, p.220) and p.21 (article p.101) images. The intro wording 'independently by Lawler and Tarjan' matches the article's credit for the directed case, while the undirected step is credited to Tarjan alone. Karp may mean the whole chain loosely, so only the author can say which attribution is intended.
Second check: another model agreed
Report a problem with this finding
Wording Problem 2 has 'integer matrix C and integer vector d', but the reduction defines 'b_i = 1 − (the number of complemented variables in C_i)' and never defines d. Appendix I lists '(a_i) (y_j) d vectors with nonnegative integer components', yet b_i is negative for clauses with two or more complemented literals.
- p. 14 Item 2, INPUT
integer matrix C and integer vector d
- p. 17 SATISFIABILITY ∝ 0-1 INTEGER PROGRAMMING
b_i = 1 - (the number of complemented variables in C_i)
- p. 23 Appendix I, Scalars, vectors, matrices
vectors with nonnegative integer components
Judge's note: Checked the p.14, p.17 and p.23 images. The symbol changes from d to b, and the Appendix's nonnegativity convention for d conflicts with both 'integer vector d' and the negative b_i the reduction produces (for example 1−2 = −1). The intent is recoverable.
Second check: another model agreed
Report a problem with this finding
Wording KNAPSACK ∝ SEQUENCING gives only "p = r, T_i = P_i = a_i, D_i = b." and never sets the penalty bound k that JOB SEQUENCING (problem 19) takes as input; the reduction works with k = Σa_i − b.
- p. 20 KNAPSACK ∝ SEQUENCING
p = r, T_i = P_i = a_i, D_i = b.
- p. 15 Item 19 JOB SEQUENCING input
positive integer k
Only the authors can say what is right here.
Judge's note: Page 20 image: no k is given. Page 15, problem 19: the input includes 'positive integer k', and the property is total penalty ≤ k. The other reductions set their parameters explicitly (k = r+1, ℓ = k, W = ...). With common deadline b, the on-time jobs have total ≤ b, so penalty ≤ Σa − b holds iff some subset sums to exactly b. The intended value can be worked out, but the map F is incompletely specified as printed.
Second check: another model agreed
Report a problem with this finding
Wording In the same reduction the arc set reads 'A = {{u_i,ū_i}| i=1,2,...,n} ∪ {{v_i,v_j}| i≠j} ∪ {{v_i,x_j}| i≠j} ∪ {{v_i,x̄_j}| i≠j} ...', using n and x_j, x̄_j although the node set N is defined with u_1..u_m, ū_1..ū_m (m ≥ 4).
- p. 19 3-SAT ∝ CHROMATIC NUMBER, arc set A
{{u_i,ū_i}| i=1,2,...,n}
- p. 19 Reduction SAT3 ∝ CHROMATIC NUMBER, arc set A
A = {{u_i,ū_i}| i=1,2,...,n} ∪ {{v_i,v_j}| i≠j} ∪ {{v_i,x_j}| i≠j}
Judge's note: The p.19 image confirms 'i=1,2,...,n' and the nodes x_j, x̄_j, which are not in N. They should be m and u_j, ū_j. The intent is recoverable.
Second check: another model agreed
Report a problem with this finding
Typo Definition of deterministic algorithm (p.87) prints 'a finite alphabet Δ such that Δ*∧R = φ' with a wedge where set intersection ∩ is meant (cf. 'Δ*∩{ACCEPT,REJECT} = φ' on p.91).
- p. 7 Definition of deterministic algorithm
Δ*∧R = φ
Judge's note: The p.7 image shows a pointed wedge ∧. The p.11 image shows the analogous condition with a rounded ∩. The intended meaning is clear, so this is cosmetic.
Second check: none (judge only)
Report a problem with this finding
Typo KNAPSACK input printed as '(a_1,a_2,...,a_r,b) ∈ Z^{n+1}' (p.95); the tuple has r+1 components, so it should read Z^{r+1}.
- p. 15 Main Theorem list, item 18 KNAPSACK
(a1,a2,...,ar,b) ∈ Z^{n+1}
- p. 15 Problem 18 KNAPSACK
(a_1,a_2,...,a_r,b) ∈ Z^{n+1}
Judge's note: The p.15 image shows the exponent n+1. n is not defined for this problem, and the reductions on p.100 use r.
Second check: none (judge only)
Report a problem with this finding
Typo Problem 19 is named 'JOB SEQUENCING' in the Main Theorem list (p.95), but Figure 1 and the reduction heading 'KNAPSACK ∝ SEQUENCING' (p.100) call it 'SEQUENCING'.
- p. 15 Item 19
JOB SEQUENCING
- p. 16 Figure 1
SEQUENCING
- p. 20 Reduction heading
KNAPSACK ∝ SEQUENCING
- p. 15 Main Theorem, problem 19
19. JOB SEQUENCING
Judge's note: The p.15, p.16 and p.20 images confirm the two names. The intended problem is clear from context.
Second check: none (judge only)