Canonical Complete Problems

SAT, graph problems, Subset Sum, and reusable patterns in NP-completeness reductions.

Goals

• Navigate the standard reduction network instead of memorizing isolated problem names.
• Match logical choice, graph compatibility, routes, cuts, colors, and arithmetic to suitable gadgets.
• Keep decision and optimization versions separate.
• Analyze binary encodings and distinguish polynomial from pseudo-polynomial algorithms.

1. The canonical network

Cook–Levin gives the starting point:

From 3SAT, clause/consistency gadgets lead to Independent Set and CLIQUE; complement and set identities connect CLIQUE, Independent Set, and Vertex Cover. Other branches lead to coloring, Hamiltonian path/cycle, Subset Sum, and Max-Cut. Hamiltonian Cycle leads naturally to the decision version of TSP; Subset Sum connects to Partition and, with stronger packing gadgets, Bin Packing.

An arrow is a theorem, not an analogy. Each requires a computable mapping, an iff proof, and a polynomial encoding bound.

2. SAT and 3SAT

SAT asks whether a Boolean formula has a satisfying assignment. 3SAT restricts input to CNF in which each clause has exactly (or, by convention, at most) three literals. SAT belongs to NP because an assignment is a certificate.

Converting an arbitrary formula to an equivalent CNF by distributivity can cause exponential blowup. The correct polynomial reduction introduces a variable for each subformula and clauses enforcing consistency—Tseitin-style encoding. Long CNF clauses are then split equisatisfiably. For example,

can become

The new formula need not be logically equivalent over the enlarged variable set; it must be equisatisfiable. Any satisfying assignment to the old clause extends to suitable $y_1,y_2$, and any satisfying extended assignment implies at least one original literal is true.

3. Independent Set, CLIQUE, and Vertex Cover

For graph $G=(V,E)$:

• IS asks whether there are at least $k$ pairwise nonadjacent vertices.
• CLIQUE asks whether there are at least $k$ pairwise adjacent vertices.
• VC asks whether at most $k$ vertices touch every edge.

All three are in NP by listing the chosen vertices and checking the relevant pairs or edges.

Complement-graph equivalence

Map $(G,k)$ to $(\overline G,k)$, where for distinct $u,v$,

Then

Constructing $\overline G$ takes $O(|V|^2)$ time in a standard representation. Loops are excluded; forgetting “distinct vertices” changes the definition.

Independent set versus vertex cover

The identity

gives

Proof. If an edge had both endpoints in $S$, $S$ would not be independent; hence every edge has an endpoint outside $S$. Conversely, if $V\setminus S$ covers every edge, no edge can have both endpoints in $S$.

The full 3SAT→IS construction and iff proof appear in the reductions lesson. Combining it with these equivalences yields NP-completeness of all three problems.

Mini-example

In the path $1-2-3-4$, $\{1,3\}$ is independent, so its complement $\{2,4\}$ is a vertex cover. In the complement graph, $\{1,3\}$ is a clique. Parameters change for VC but not for CLIQUE.

4. Coloring

$k$-COLOR asks whether vertices can be assigned one of $k$ colors so adjacent vertices differ. A color vector is a polynomial certificate. For $k=2$, BFS decides the problem by testing bipartiteness; for every fixed $k\ge3$, the problem is NP-complete.

A reduction from 3SAT to 3-COLOR typically creates a fixed palette triangle named True, False, and Base. Variable gadgets force a choice between True and False, while clause gadgets are colorable exactly when at least one incident literal carries True. The exact clause gadget matters: a drawing that “looks constrained” is not a proof. One must show both how every satisfying assignment extends to a coloring and how every legal coloring decodes a satisfying assignment.

Do not silently vary $k$. “3-COLOR” and “COLORING with $k$ in the input” are different languages, though both are NP-complete.

5. Max-Cut

Decision MAX-CUT receives $(G,K)$ and asks whether some partition $(S,V\setminus S)$ has at least $K$ crossing edges. The optimization version asks for the maximum number (or weight) of crossing edges. NP-completeness claims concern the decision language.

A partition is a certificate; count crossing edges in polynomial time. In a triangle, every cut crosses at most two edges, and placing one vertex on one side and two on the other achieves two. Thus $(K_3,2)$ is yes and $(K_3,3)$ is no.

Reductions to Max-Cut use edges as rewards for opposite truth values. Heavy or replicated edges can pin reference vertices or dominate auxiliary choices. If weights are used, their binary sizes and the conversion to an unweighted instance must be analyzed; replacing weight $W$ by $W$ parallel structures is polynomial only when $W$ itself is polynomially bounded.

6. Hamiltonian problems and TSP

Hamiltonian Path asks for a simple path visiting every vertex exactly once; Hamiltonian Cycle requires returning to the start. A certificate is an ordering of vertices. Verify uniqueness and each consecutive edge, plus the closing edge for a cycle.

Standard reductions use variable tracks that can be traversed in two directions, representing truth values, and clause detours reachable only from a track corresponding to a satisfied literal. The invariant is global: a Hamiltonian traversal must choose one consistent track per variable while visiting every clause gadget.

The directed and undirected variants require different gadgets. A proof must name which variant is the source and target.

Hamiltonian Cycle to decision TSP

Given an unweighted graph $G=(V,E)$, form the complete graph on $V$ with

Set budget $B=|V|$. If $G$ has a Hamiltonian cycle, its edges give a tour of weight $|V|$. Conversely, every tour has exactly $|V|$ edges, each of weight at least one; a tour of weight at most $|V|$ must use only weight-one edges and therefore is a Hamiltonian cycle in $G$.

The construction has $O(|V|^2)$ edges and tiny weights, so it is polynomial. This proves hardness of the decision language “is there a tour of weight at most $B$?” Membership in NP follows by listing the tour and adding binary weights.

7. Subset Sum and numeric encodings

SUBSET-SUM receives nonnegative binary integers $a_1,\ldots,a_m,T$ and asks whether

A certificate is an $m$-bit selection vector. Binary addition is polynomial in total bit length.

The instance

is yes because $3+5+6=14$. With target $13$, exhaustive inspection is not a complexity proof; it only settles this tiny instance.

No-carry encodings

The reduction from 3SAT assigns digit columns to variables and clauses. Numbers representing choosing literal $x_i$ or $\neg x_i$ place controlled digits in the variable column and in clauses where that literal occurs. Additional slack numbers fill clause columns. The target asks for one truth choice per variable and enough clause contribution to certify at least one satisfied literal.

Choose a base larger than the maximum possible column sum. Then no carries occur, and decimal-looking arithmetic decomposes into independent column constraints. If there are polynomially many columns and each digit has constant range, every generated number has polynomially many bits:

The proof must establish this bound; merely displaying huge integers is not enough.

Pseudo-polynomial dynamic programming

The familiar table indexed by target values runs in $O(mT)$ time. With $T$ encoded in binary, $T$ can be exponential in $\log T$, so this is pseudo-polynomial, not polynomial in input length. If values are unary encoded or polynomially bounded, the interpretation changes. Encoding is therefore part of the theorem.

8. Partition and Bin Packing

PARTITION asks whether the numbers can be split into two groups of equal sum. For total $S$, odd $S$ is immediately no; when $S$ is even, it asks for a subset summing to $S/2$. This shows the structural relation to Subset Sum, but a many-one hardness proof from arbitrary Subset Sum needs a balancing construction; writing target $S/2$ reverses the easy direction or handles only a special case.

Complete reduction from Subset Sum to Partition

Take a SUBSET-SUM instance $a_1,\ldots,a_m,T$ and let $S=\sum_i a_i$. Reject trivial malformed or out-of-range cases separately; if $T>S$, emit a fixed no-instance. Otherwise add

The new multiset has total

so each side of a partition must sum to $2S$. If original numbers with sum $T$ exist, place them together with $x$ on one side; their sum is $T+(2S-T)=2S$. Conversely, neither side can reach $2S$ using only original numbers, whose total is $S$, and $x+y=3S$ cannot fit together on one side. Thus one side contains exactly one of $x,y$. If it contains $x$, its original numbers sum to $T$. If it contains $y$, they sum to $S-T$, so the complementary original numbers sum to $T$. This proves the iff.

The generated values are at most $3S$. Their bit lengths are $O(\log S)$, and $\log S$ is at most the total input bit length plus $O(\log m)$. Computing the sums and printing the two numbers is polynomial. This is the encoding analysis that turns the arithmetic identity into a valid reduction.

BIN PACKING decision receives item sizes, bin capacity $C$, and number of bins $b$, and asks whether all items fit into at most $b$ bins. A certificate assigns each item to a bin; verify every capacity sum.

Partition is the two-bin special structure when total size is exactly $2C$. Stronger NP-hardness results for Bin Packing use problems such as 3-PARTITION, whose instances force exactly three items per bin through size bounds. This distinction matters: a pseudo-polynomial algorithm for weakly NP-complete numeric problems does not contradict strong NP-hardness.

Mini-example: items $6,4,5,5$ fit into two bins of capacity $10$ as $(6,4)$ and $(5,5)$. Items $6,6,4,4,1$ have total $21>20$, so the same two-bin instance is immediately no.

For the Subset-Sum instance $\{3,5,6\}$ with $T=8$, $S=14$, so add $x=20$ and $y=22$. The Partition total is $56$ and each side needs $28$. The subset $\{3,5\}$ joins $20$, while $\{6,22\}$ forms the other side.

9. Small cut and coloring gadgets

A useful Max-Cut micro-gadget is a length-two path $u-a-v$. If $u$ and $v$ lie on the same side, placing $a$ on the other side cuts both edges; if they lie on opposite sides, at most one edge is cut. Thus the gadget rewards equality of the terminals by two versus one. A direct edge $uv$, by contrast, rewards inequality. Weighted combinations of these two effects express Boolean constraints, provided the proof sets a threshold that leaves no slack for violating a required gadget.

For coloring, a triangle forces three different colors. Once its vertices are named $T,F,B$, connect a variable vertex to $B$ so it can use only $T$ or $F$; connect a second vertex representing its negation so the pair is forced to opposite truth colors. A complete clause gadget must then forbid only the all-false combination while remaining colorable for each of the other seven combinations. Checking those cases, or proving a structural invariant that covers them, is the coloring analogue of an iff proof.

These examples explain the pattern without substituting for a full reduction. Every shared auxiliary vertex and every unintended coloring or cut must be included in the reverse-direction analysis.

10. Choosing a source problem

Choose a source whose solution structure resembles the target:

• local Boolean choices and consistency: 3SAT;
• pairwise compatibility or conflict: CLIQUE/IS;
• selecting objects under exact arithmetic: Subset Sum;
• cyclic global traversal: Hamiltonian Cycle;
• partitioning by disagreement: Max-Cut;
• bounded groups and capacities: 3-Partition or Bin Packing.

The nearest-looking source is not automatically valid, but a good structural match makes the invariant and reverse proof easier.

Common mistakes

1. Switching silently between decision and optimization.
2. Omitting $k$, $K$, $B$, capacity, or number of bins from an instance.
3. Treating arithmetic operations or loops to $T$ as constant/polynomial in $\log T$.
4. Claiming direct CNF expansion is always polynomial.
5. Giving only the intuitive direction of a gadget.
6. Confusing graph complement with set complement.
7. Using a directed Hamiltonian gadget for an undirected target.
8. Claiming every structural relation is already a hardness reduction.

Exercises

Exercise 1 — IS→VC parameter

Prove the equivalence: $G=(V,E)$ has an independent set of size $\ge k$ iff it has a vertex cover of size $\le |V|-k$.

Exercise 2 — Unit-weight TSP budget

In a reduction from Hamiltonian Cycle to TSP with weight $1$ on graph edges and large weight on non-edges, why is budget $|V|$ correct?

Exercise 3 — Large base in Subset Sum

Explain why a large base (e.g. $4$) is needed in a 3SAT→Subset Sum reduction.

Exercise 4 — $O(mT)$ with binary $T$

Prove that an $O(mT)$-time Subset Sum algorithm need not be polynomial when $T$ is binary-encoded.

Exercise 5 — After hardness: NP membership

A student proves $A$ is NP-hard but forgets $A\in\mathrm{NP}$. What is missing for completeness? Why is 2-COLOR not a valid NP-complete target unless $\mathrm P=\mathrm{NP}$?

Summary

Canonical problems form a reduction network. Parameters, weights, and numeric encodings are common places for formal mistakes.

Guided practice

Task 1 — CLIQUE↔IS

Prove a polynomial equivalence between CLIQUE in $G$ and IS in $\overline G$ (or vice versa) with the same $k$.

Task 2 — Choosing a source problem

When is it better to start a reduction from 3SAT versus from Vertex Cover? Give a short criterion.

Task 3 — Coloring encoding trap

Explain why a reduction to $k$-COLOR must handle the exact language definition (is $k$ fixed or part of the input?) used in the course.

Sources

Course evidence

• Current Semester A transcript 14: graph gadgets and the Hamiltonian/TSP material used here.
• Current Semester A transcript 15: the numeric-problem material, including Subset Sum, Partition, and encoding cautions.
• Merged course summary, pp. 55–57, 64–66, and 72–75: only the graph-problem family and its reductions (including the applicable independent-set, clique, vertex-cover, coloring, and cut material).
• The Hamiltonian/TSP and Subset-Sum/Partition/Bin-Packing sections are transcript-and-textbook syntheses. They are not attributed to the merged summary.

Textbook verification

• Sipser, Introduction to the Theory of Computation, 3rd ed., §7.5, pp. 315–325: 3SAT and selected graph reductions.
• Papadimitriou, Computational Complexity, Ch. 9: canonical NP-complete graph, route, and numeric problems.
• Garey–Johnson, Computers and Intractability, Ch. 3 and the problem catalog: standard formulations, encoding qualifications, and reduction families. These references verify theorem statements; examples and organization above follow the course.