Reductions

A reduction turns one problem into another. It is how hardness is proved: if every input of a known hard problem can be rewritten as an input of your problem, your problem is at least as hard. It is also a practical tool: rewrite your problem as one that has an excellent solver, and use the solver.

What a reduction is

A reduction from problem A to problem B is a function f that turns any question x about A into a question f(x) about B, such that:

Then a method for B solves A: compute f(x), ask B. If B is fast, so is A. Turned round: if A is hard, B must be hard too. So to prove B is NP-hard, reduce a known NP-hard problem to B, not the other way. The direction is the most common slip.

A proof of a reduction always has three parts:

1. the construction of f(x), and why it takes polynomial time;
2. yes for x ⟹ yes for f(x): turn an answer for x into an answer for f(x);
3. yes for f(x) ⟹ yes for x: turn any answer for f(x) back into an answer for x.

Part 3 is the one people forget. It says the construction adds no new answers: no answer for f(x) exists unless x has one.

3-SAT to independent set

An independent set is a set of vertices with no edge between any two of them. The decision problem: does a graph have an independent set of size k? Reduce 3-SAT to it. A clause is a bracket of conditions joined by “or”, such as (x₁ ∨ ¬x₂ ∨ x₃); ∨ means “or”, ∧ means “and”, ¬ means “not”. Given a formula with m clauses:

• for each clause, make a triangle with one vertex per condition;
• join every vertex x to every vertex ¬x, in any triangle;
• ask for an independent set of size m.

def sat_to_independent_set(clauses):
    # clauses: lists of 3 literals, k for x_k and -k for not x_k
    vertices = [(c, lit) for c, clause in enumerate(clauses) for lit in clause]
    edges = []
    for i, (c1, l1) in enumerate(vertices):
        for j in range(i + 1, len(vertices)):
            c2, l2 = vertices[j]
            if c1 == c2 or l1 == -l2:     # same triangle, or opposites
                edges.append((i, j))
    return len(vertices), edges, len(clauses)   # n, edges, k

The graph has 3m vertices and at most 3m + (3m)²/2 edges, built in polynomial time. The two directions are in the figure: an assignment gives one true condition per triangle, which form an independent set; an independent set of size m has one vertex per triangle and never a condition with its opposite, so making its conditions true is consistent and satisfies every clause. Independent set is in NP (check the set), so it is NP-complete.

Independent set, vertex cover and clique

Some reductions are a single line once the right observation is made.

• Vertex cover. S is independent exactly when the other vertices, V − S, touch every edge: an edge with both ends outside the cover would have both ends in S. So a cover of size V − k exists ⟺ an independent set of size k exists.
• Clique (a set where every two vertices are joined). S is independent in G exactly when S is a clique in the complement of G, the graph with an edge wherever G has none.

So all three are NP-complete, and a fast method for any one would give the other two.

More reductions, in outline

• Three-colouring (GRPH-6’s three groups). A triangle of three special vertices fixes the meaning of the groups: True, False and Base. Each variable becomes a pair x, ¬x joined to each other and to Base, so one is True and the other False. Each clause gets a small gadget of six vertices that can be coloured exactly when at least one of its three inputs is True.
• Subset sum. Write numbers in base 10 with one digit place per variable and one per clause. Choosing a number means making a condition true; the target forces exactly one of x, ¬x per variable, and at least one true condition per clause (with small padding numbers). No carries can happen, so digit places act separately.
• Travelling salesman. From Hamiltonian cycle: give each edge of the graph length 1 and each missing pair length 2. A tour of length n exists ⟺ the graph has a Hamiltonian cycle. The same idea shows that no approximation ratio is possible for tours without the triangle rule (lesson 4).
• Bin packing (the fewest wagons, ADDP-P4). From partition (split numbers into two halves of equal sum): two wagons of half the total each are enough ⟺ the split exists.

Reducing to SAT

Cook–Levin says every problem in NP reduces to SAT. In practice, that is a way of solving: write your problem as clauses and hand them to a SAT solver. Modern solvers (they learn new clauses from each dead end) handle millions of clauses for many real problems: chip checking, timetables, puzzles. In Python, pycosat and python-sat wrap such solvers, and Google’s OR-Tools has CP-SAT.

The usual building blocks, with a variable for each yes/no fact (“vertex v gets group c”):

• at least one of a, b, c: one clause (a ∨ b ∨ c);
• at most one: a clause (¬a ∨ ¬b) for every pair;
• not both (a rule between two facts): (¬a ∨ ¬b);
• if a then b: (¬a ∨ b), as in 2-SAT (CONN-4).

The practice problem asks for the formula that says “this graph splits into three groups with no edge inside a group”. Its tests check both directions on small graphs by solving your formula, and on large ones that a planted split passes while every broken split fails.

Common slips

• The wrong direction. Reducing your problem to SAT shows only that your problem is in NP, not that it is hard.
• Only one direction of the “⟺”. Without part 3, f could map every question to an easy yes.
• A construction that solves the problem. If f must find the answer to build its output, it is not polynomial, unless the problem was easy all along.
• Numbers that grow too long. A construction must write its numbers in polynomially many digits; writing a number n as n marks is exponential in its length.

Now try HARD-P2, Three groups as a formula.