Lesson · Intractability and Approximation · Deciding, verifying, searching

A Reduction Is a Construction

“Satisfiability reduces to independent set” is a sentence that can be repeated and cannot be used. The reduction is a construction: a triangle per clause, an edge between contradictory literals, and a target equal to the number of clauses. The lab builds it, solves both sides exhaustively, and then asks the question a diagram with an arrow on it cannot — what the map does to the solutions, which is three questions and not one.

Open the interactive lesson Practice

f is a polynomial-time map on INSTANCES with x ∈ A ⟺ f(x) ∈ B one vertex per literal OCCURRENCE, a triangle per clause, an edge between every contradictory pair, and k = the clause count 2 clauses → 6 vertices, 8 edges, k = 2 7 independent sets of size 2 against 6 satisfying assignments sound: yes. injective: no, one assignment has three preimages. onto: no, 111 is unhit

The gadget, and the three separate verdicts on the map it induces

Core ideas

What this lesson establishes

The first idea is what a reduction has to preserve, which is less than readers expect. The second is the gadget: two constraints expressed as edges. The third is the distinction the page computes three times rather than asserting once.

A reduction preserves the ANSWER, not the solutions

Writing A reduces to B means there is a polynomial-time map f on instances with the property that x is a yes instance of A exactly when f(x) is a yes instance of B. That is a statement about two bits. It does not say the solution sets correspond, and a reader who assumes they do will believe things about this reduction that the lab shows to be false. Preserving the solutions one for one is a stronger property that some reductions have and this one does not.

The gadget turns two requirements into two kinds of edge

A satisfying assignment picks one true literal from each clause, and never picks a literal and its negation. Those are exactly the two things an independent set cannot do if you build the graph correctly: put the three literal occurrences of a clause in a triangle, so at most one of them can be chosen, and join every occurrence of x to every occurrence of ¬x, so a contradictory pair can never both be chosen. An independent set of size m then picks exactly one literal from each of the m clauses, consistently — which is an assignment.

Sound, injective and onto are three questions

The panel answers them separately because their answers differ. Every independent set of size k maps back to an assignment that satisfies the formula: sound. Two different sets can map to one assignment, and here three do: not injective. And an assignment can fail to be the image of anything, because the map back leaves every variable no chosen literal mentions at false: not onto. One word could not have carried any of that.

The material

The map on instances, the gadget, and the map it induces on solutions

What a reduction is, the two edge types, the correctness proof in both directions, and the three verdicts the lab computes on the induced map.

Definition · Polynomial-time many-one reduction

A reduces to B, written A ≤p B, when there is a function f computable in polynomial time taking instances of A to instances of B such that x is a yes instance of A if and only if f(x) is a yes instance of B. The direction of the consequence is the part to hold on to: an algorithm for B gives one for A, so hardness travels from A to B and tractability travels the other way.

Definition · Independent set

An independent set in a graph is a set of vertices no two of which are joined by an edge. The decision problem takes a graph and an integer k and asks whether one of size k exists. The lab's target k is always the number of clauses, which is what makes the construction a reduction rather than a drawing.

The construction

One vertex for each literal occurrence, not one per literal. A clause with three literals contributes three vertices even if two of them name the same variable.
An edge between every two vertices of the same clause, making a triangle. At most one vertex per clause can be in an independent set.
An edge between every occurrence of x and every occurrence of ¬x. No independent set can hold two occurrences that contradict.
Ask for an independent set of size k = m, the number of clauses.

Theorem · The construction is a reduction

The formula is satisfiable if and only if the constructed graph has an independent set of size m.

Suppose the formula is satisfiable. Fix a satisfying assignment and, in each clause, choose one occurrence of a literal the assignment makes true. The chosen vertices lie in distinct clauses so no triangle edge joins two of them, and they are all true under one assignment so no contradiction edge joins two of them either. That is an independent set of size m.

Conversely, suppose there is an independent set S of size m. The triangles force its members into distinct clauses, one each. Set every variable so that each literal named by a member of S is true; this is consistent, because a variable asked to be both true and false would mean S contains a contradictory pair, and those are joined. Variables no member mentions may be set arbitrarily. Each clause now contains a true literal, so the formula is satisfied.

□

Both halves are needed and the second is the one that gets skipped. A construction with only the first half proves that a yes instance maps to a yes instance, which permits a map that turns every no instance into a yes instance as well — and is therefore useless. The lab checks both directions on every solution, not once on the optimum.

What the lab built, and what it then measured

The loaded formula is (x1 or x2 or not x3) and (not x1 or x2 or x3): two clauses, three variables. The construction gives 6 vertices and 8 edges — two triangles for six of them, plus x1 to ¬x1 and ¬x3 to x3 — and k = 2. There are 15 pairs of vertices and 8 are joined, so exactly 7 pairs are independent, and the panel reports 7 independent sets of size 2 against 6 satisfying assignments.

Those two counts are not equal, and nothing requires them to be. What the reduction promises is that one list is empty exactly when the other is. What the panel computes is the whole map between them: sound in both directions, three sets landing on one assignment, and one assignment that is the image of nothing.

Two rows of that table look as though they disagree and do not, and it is worth reading them together. The reverse construction succeeds on every model — take the first true literal of each clause and all 6 give an independent set of size 2 — while the map back is not onto. Both are true because the round trip is not the identity: starting from the all-true assignment, the first true literals are x1 in the first clause and x2 in the second, so the set built is the pair of vertices 1 and 5, and that set reads back as x1=T x2=T x3=F. Every model builds a set; not every model is what the set it builds maps back to.

Example · Why 111 is unreachable

The assignment making all three variables true satisfies both clauses, so it is a model. But an independent set here has 2 members, so at most 2 variables can be named by a chosen literal, and the map back leaves every unmentioned variable false. Three true variables therefore cannot be the image of a 2-element set. The gap is a property of the map, not an error in it: the reduction was never required to be onto.

This is the first place on this course where a measured fact and a proved claim point in different directions, and the lesson is to read each for what it is. The proof establishes that the two yes-or-no answers agree, for every formula. The panel establishes that on this formula the map on solutions is three-to-one somewhere and misses one assignment. Neither statement is evidence about the other.

Interactive

3-SAT to independent set, gadget by gadget

A triangle per clause and an edge between contradictory literals — the graph is built here, a set is carried back, and the map is checked in both directions

Step through the independent sets and watch two of them give one assignment

Both problems are solved exhaustively: every independent set of size k, and every satisfying assignment. The map between them is checked for soundness, for surjectivity and for injectivity separately, because this reduction has the first and not the other two — and it is correct anyway.

Worked example

Clauses, literals by spaces and clauses by a semicolon

Which independent set to carry back1

The formula—

The graph built from it—

k, which is the clause count—

Independent sets of size k—

Satisfying assignments—

Every set maps to a model—

Every model builds a set—

Two sets sharing one model—

One vertex per occurrence of a literal, not per literal. The three vertices of a clause form a triangle, so an independent set can take at most one from each clause; an edge joins x to ¬x wherever they occur, so it can never take two that contradict. An independent set of size k = m therefore takes exactly one true literal from every clause, and reading those literals off is an assignment.

Method

Building a reduction, and checking the thing you built

Four of these five steps are things a diagram with an arrow on it silently skips.

Write the map on instances, with its running time

Say exactly what is built from what: how many vertices, which edges, what target. If the construction cannot be described without the phrase “and so on”, it has not been written down yet. The time bound matters as much as the output, because an exponential map proves nothing about hardness.

Prove the forward direction by construction

Take a solution of the original and build a solution of the transformed instance from it. This is the half that says the construction can represent what it claims to represent, and it is the one a page that only maps solutions back never tests.

Prove the backward direction by reading off

Take a solution of the transformed instance and read a solution of the original out of it, then check that solution by the original problem's own rules. The lab carries each independent set back and evaluates the formula clause by clause on the result.

Ask the three questions about the induced map separately

Is every image a genuine solution? Do two solutions share an image? Is every solution an image? The answers are independent of one another and only the first is required for the reduction to be valid. Writing “bijection” without computing the other two is how a false claim gets into a correct proof.

Check the no case as well as the yes case

Load the unsatisfiable example in the panel: the largest independent set in the constructed graph is 3 against a target of 4, so the answer is no on both sides. A reduction tested only on yes instances has been tested on half the definition.

What a reduction promises, and what it does not

Score 0 / 0

Choose the answer you can justify.

Two clauses, six vertices, and the seven sets carried back

Vertices 1, 2, 3 are the occurrences of x1, x2, not x3 in the first clause; vertices 4, 5, 6 are not x1, x2, x3 in the second. The map back sets every variable named by a chosen literal and leaves the rest false.

edges 1-2 1-3 2-3 the first clause's triangle 4-5 4-6 5-6 the second clause's triangle 1-4 x1 against ¬x1 3-6 ¬x3 against x3 15 pairs of vertices, 8 of them joined, so 7 independent pairs: set literals chosen assignment read back {2, 4} x2 , ¬x1 010 {3, 4} ¬x3 , ¬x1 000 {1, 5} x1 , x2 110 {2, 5} x2 , x2 010 {3, 5} ¬x3 , x2 010 {1, 6} x1 , x3 101 {2, 6} x2 , x3 011 every one of the 7 satisfies the formula sound three sets land on 010 not injective the 6 models are 000 010 110 101 011 111; 111 is the image of nothing not onto

The three sets landing on 010 are the clause-with-two-true-literals case. Under 010 the first clause is satisfied by x2 and by not x3, and the second by x2, so there is more than one way to choose a witness and each choice is a different independent set. Nothing distinguishes them and the map back cannot see the difference.

The unhit model is the other failure of symmetry, and it has a different cause. Two chosen literals can make at most two variables true, so a model with three true variables has no preimage. Adding a third clause changes this: the panel's three-clause example has 9 vertices, 12 independent sets of size 3, 5 models, and every model is hit.

For a faded rehearsal, switch to the formula with a repeated literal and predict the vertex count before running it. The supplied first move: vertices count occurrences, so a clause writing x1 twice still contributes three. Say how many edges that clause's triangle contributes and whether the two copies can both be chosen, then check.

Common mistakes

Writing bijection over an arrowIt is the single most common false claim about reductions, and no markup check anywhere would catch it. Of the reductions built on this course some do induce a bijection on solutions and some do not, and the only way to know which is to enumerate both sides and compare them as sets.

Proving only that a solution maps backSoundness alone permits a construction that turns a no instance into a yes instance, which destroys the reduction while leaving every mapped-back solution genuine. The forward half — building a solution of the transformed instance from each solution of the original — is the half that rules that out.

Counting literals instead of occurrencesThe gadget needs one vertex per occurrence. Merging the two copies of a repeated literal into one vertex changes the triangle, changes the target, and breaks the argument that an independent set of size m touches every clause. The panel's repeated-literal example is there to be tried for this reason.

Check your understanding

✓

Finish when you can build the graph from a formula on paper and say what the induced map does.

You should be able to state the definition of a polynomial-time reduction and the direction hardness travels, construct the triangles and contradiction edges for a formula of your own, prove both directions, and give the three verdicts on the induced map separately with a reason for each.

Note: The three verdicts here were computed on one formula. “What the Solution Map Preserves” adds a single clause to it and watches one of the three change, which is this Subject's hazard arriving at the level of a proof rather than a count.