Karp Reductions, in depth: many-one versus Cook reductions, Karp's 21 problems, and a tested 3-SAT to 3-colouring reduction

What a Karp reduction must satisfy

Let A and B be decision problems, sets of yes-instances over strings. A Karp reduction, also called a polynomial-time many-one reduction and written A ≤p B, is a function f with three properties:

1. f is computable in polynomial time in the size of its input. That also bounds the output: f(x) has polynomial size, because a polynomial-time program cannot write more.
2. Completeness: if x is a yes-instance of A, then f(x) is a yes-instance of B.
3. Soundness: if f(x) is a yes-instance of B, then x is a yes-instance of A. This is the contrapositive of no-maps-to-no, and it is the direction people forget.

The consequence is the one you use. If B has a polynomial algorithm, so does A: compute f(x) and ask B. Read the other way, if A is NP-hard, B is NP-hard too. So to show your problem B is hard, you reduce a known hard problem A to B, never B to A. Reducing your problem to SAT shows only that SAT is at least as hard as yours, which everyone already knew.

Note what f is not allowed to do. It gets one call to B, at the end, and must pass B's answer through unchanged. It cannot negate the answer, combine several calls, or peek at whether x is a yes-instance. Exponential-time preprocessing is also out, even when it would be fast on your test cases.

Karp versus Cook reductions

Stephen Cook's 1971 paper, which proved SAT NP-complete, used a more generous notion: a polynomial-time Turing reduction, now often called a Cook reduction. A Cook reduction solves A in polynomial time with a B oracle that it may call many times and whose answers it may combine freely. Leonid Levin reached the same theorem independently.

The table's fourth row is the practical difference. Under Cook reductions a problem and its complement reduce to each other, so the notion cannot tell NP from coNP. Karp reductions keep that distinction, which is why NP-completeness is defined with them. Whether the two notions give the same class of NP-complete problems is an open question.

Cook reductions are still the right tool for optimisation. Finding a maximum clique reduces to the decision version by binary search on k plus self-reduction (delete a vertex, ask again, keep it if the answer drops). That uses many calls, so it is a Cook reduction, and it is how you show the search problem is no harder than the decision problem.

Karp's 21 problems and the reduction tree

Karp's 1972 paper, Reducibility Among Combinatorial Problems, showed that 21 problems are NP-complete by arranging reductions in a tree rooted at SAT. The diagram reproduces part of it. Every edge is one Karp reduction, and because the composition of two polynomial-time maps is polynomial, a single proof at each edge makes every box hard.

Two lessons from the tree carry over to your own proofs. First, choose a source that already looks like your problem. Covering problems come from NODE COVER, ordering problems from Hamiltonian circuits, numeric problems from PARTITION or KNAPSACK, and problems with local constraints from 3-SAT. Second, the numeric problems at the bottom (KNAPSACK, PARTITION) are hard only when the numbers are written in binary. A reduction that creates exponentially large numbers proves weak NP-hardness, and a pseudo-polynomial dynamic programme can still solve the problem in practice. The NP-complete catalogue covers that strong-versus-weak split and has a reference card of source problems.

Worked reduction: 3-SAT to 3-colouring

Here is a full reduction that the other pages do not cover: 3-SAT to 3-COLOURING. The input is a CNF formula with n variables and m clauses of three literals. The output is a graph that is 3-colourable exactly when the formula is satisfiable. The construction is the textbook one, not Karp's original (he reduced to CHROMATIC NUMBER differently).

• Palette. A triangle on vertices T, F and B. In any 3-colouring they get three different colours, so we can name the colours after them: true, false and base.
• Variables. For each variable x, vertices x and ¬x joined to each other and both joined to B. Neither can be base, and they differ, so exactly one is coloured true. That is an assignment.
• Clauses. An OR gate takes inputs a and b and adds a triangle u, v, w with edges a–u and b–v. Its output w can be coloured true when at least one input is true. When both inputs are false, u and v must use true and base, so w is forced to false. Chain two gates to get OR(OR(a, b), c), then join the final output to F and B, which forces it to be true.

Completeness: given a satisfying assignment, colour each literal by its truth value. Every clause has a true input, so each gate chain can output true, and the graph is coloured. Soundness: given a 3-colouring, read x as true when its colour matches T's. Each clause's final output is true, which is impossible if all three inputs are false, so every clause has a true literal. The size is 3 + 2n + 6m vertices and 3 + 3n + 12m edges, linear in the formula, so the polynomial-time condition holds with room to spare.

The reduction as tested code

Writing the reduction as code turns a paper proof into something you can test. The function below is the whole of f. The test compares f's answer against brute force and checks that every colouring found decodes back into a satisfying assignment.

def reduce_3sat_to_3col(n, clauses):
    """Literals are +i / -i for variable i in 1..n. Returns (num_vertices, edges, names)."""
    names, edges = {}, set()

    def vid(name):
        if name not in names:
            names[name] = len(names)
        return names[name]

    def edge(a, b):
        edges.add((min(a, b), max(a, b)))

    T, F, B = vid("T"), vid("F"), vid("B")
    edge(T, F); edge(F, B); edge(B, T)
    for i in range(1, n + 1):
        p, q = vid(("lit", i)), vid(("lit", -i))
        edge(p, q); edge(p, B); edge(q, B)

    def or_gate(a, b, tag):
        u, v, w = vid(tag + ("u",)), vid(tag + ("v",)), vid(tag + ("w",))
        edge(a, u); edge(b, v); edge(u, v); edge(v, w); edge(w, u)
        return w

    for j, (a, b, c) in enumerate(clauses):
        o1 = or_gate(vid(("lit", a)), vid(("lit", b)), ("c", j, 1))
        o2 = or_gate(o1, vid(("lit", c)), ("c", j, 2))
        edge(o2, F); edge(o2, B)            # force the clause output to "true"
    return len(names), sorted(edges), names

def colouring_to_assignment(col, names, n):     # the soundness witness map
    t = col[names["T"]]
    return tuple(col[names[("lit", i)]] == t for i in range(1, n + 1))

The harness generates random 3-CNF formulas with 3 to 5 variables and up to 4n + 2 clauses. For each one it asserts the vertex and edge counts, decides satisfiability by trying every assignment, and decides 3-colourability with an exact checker. Because gadgets touch only the palette and the literal vertices, the checker fixes the palette, tries every literal colouring and brute-forces each six-vertex gadget separately. On 400 formulas (387 satisfiable, 13 unsatisfiable) the two answers agreed every time, and every colouring decoded to a satisfying assignment. The unsatisfiable formula made of all eight sign patterns over three variables becomes a 57-vertex, 108-edge graph, and the checker confirms it has no 3-colouring.

Test the unsatisfiable side deliberately. Random formulas at low clause density are almost all satisfiable, so a reduction that maps everything to a colourable graph would pass most of them. That is why the hand-built eight-clause formula is in the suite.

Blow-up, parsimony and witness maps

Three properties of reductions matter once you compose them or use them as solvers.

• Blow-up compounds. If f has output size O(n²) and g has O(n³), then g∘f has O(n⁶). The result is still polynomial, but it can be useless in practice. For a reduction you plan to run, aim for linear or near-linear size, as the 3-COLOURING one is.
• Parsimony. A reduction is parsimonious if it preserves the number of solutions. That matters for counting problems (#P) and for uniqueness claims. The reduction above is not parsimonious. Any colouring can permute its three colours, which multiplies the count by 6, and a gate with two true inputs can be coloured in more than one way.
• Witness maps. A decision reduction says nothing about recovering a solution. For engineering use, also write the backward map from a target solution to a source solution (colouring_to_assignment here) and test it. Without it, a SAT solver's model is just bits.

The forward direction is how hard problems actually get solved. Encoding your problem into SAT, MaxSAT or an integer program is a Karp reduction from your problem to theirs, and solvers then exploit decades of engineering. SAT solving covers the Tseitin encoding, which is itself a linear-size reduction from circuit satisfiability to CNF whose models match the circuit's satisfying inputs one to one. Going the other way, a 3-COLOURING instance from graph colouring work becomes CNF with one variable per vertex and colour, at-least-one and at-most-one clauses per vertex, and one clause per edge and colour.

A threshold reduction: Hamiltonian cycle to TSP

A second, smaller reduction shows how the threshold does the work. Hamiltonian cycle reduces to the decision version of the travelling salesman problem: given a graph G on n vertices, build a complete graph with weight 1 on G's edges and weight 2 on every non-edge, and ask whether a tour of cost at most n exists. A tour of cost n uses only weight-1 edges, so it is a Hamiltonian cycle of G, and any Hamiltonian cycle of G is such a tour. Replace 2 by a huge number and the same argument shows that no polynomial algorithm can approximate general TSP within any constant factor unless P = NP. Weights 1 and 2 satisfy the triangle inequality, so the basic reduction already makes metric TSP NP-hard. Only the huge-weight version breaks the inequality, which is why metric TSP escapes the inapproximability result and has constant-factor approximations.

Failure modes

Most broken reductions fail in one of these ways.

• Wrong direction. Reducing your problem to a known NP-complete one proves nothing about hardness. Write A ≤p B with your problem as B before starting.
• One-way proof. Only completeness is shown. A gadget that admits a cheating solution, such as a variable that is true and false at once, fails soundness. Prove soundness first, because it is where gadgets break.
• Hidden exponential size. The output enumerates assignments or subsets, or writes a number in unary that was binary in the input.
• Using the answer. The construction branches on whether the input is a yes-instance. That makes it a decision procedure, not a reduction.
• Wrong source variant. The source is accidentally an easy special case, such as 2-SAT, Horn-SAT or a bipartite graph, so its hardness is not established.
• Untested witness map. The decision answers agree but decoded solutions are wrong, which only shows up when someone uses the encoding in production.

In engineering use, test encodings the way the harness above does: random small instances, a brute-force oracle on both sides, deliberately unsatisfiable cases, and a decoded-solution check. Run it in CI, because encodings get edited.

What to do next

1. Write the definition from memory with all three obligations, and say which one the contrapositive covers.
2. Run the 3-SAT to 3-COLOURING code above and add more unsatisfiable cases, such as all eight sign patterns over a different variable triple, or random formulas at high clause density.
3. Implement the Hamiltonian cycle to TSP map and check it against a brute-force tour search on graphs with up to 8 vertices.
4. For a problem you actually need to solve, write its forward encoding to CNF together with its witness decoder, and give both a brute-force test.
5. For a problem you suspect is hard, choose a source from Karp's tree that resembles it, write the gadgets, and prove soundness before completeness.
6. Classify any hardness claim you rely on as Karp or Cook, and as strong or weak, before deciding whether an exact or pseudo-polynomial algorithm is worth trying.