A Tour of Classic NP-Complete Problems

A problem $L$ is NP-complete if $L \in \mathrm{NP}$ and every problem in NP polynomial-time reduces to $L$. The Cook–Levin theorem gives the seed: Boolean satisfiability (SAT), and its restricted variant 3-SAT (formulas in conjunctive normal form with exactly three literals per clause), is NP-complete because a nondeterministic Turing machine's computation history can be encoded as a Boolean formula whose satisfying assignments correspond exactly to accepting computations. Once one NP-complete problem $L_1$ is known, a new problem $L_2 \in \mathrm{NP}$ is proven NP-complete by exhibiting a polynomial-time reduction $L_1 \le_p L_2$: a function $f$, computable in polynomial time, such that $x \in L_1 \iff f(x) \in L_2$. Because polynomial-time reductions compose (if $L_1 \le_p L_2$ and $L_2 \le_p L_3$ then $L_1 \le_p L_3$), and because every problem in NP already reduces to $L_1$, transitivity forces every problem in NP to reduce to $L_2$ as well. This is the mechanism by which NP-completeness "spreads" — a single reduction step attaches an entire new problem to the growing web rooted at SAT. The art of proving NP-completeness is almost entirely the art of designing gadgets: small, local pieces of structure that simulate one combinatorial primitive (a Boolean variable, a clause, a choice) inside the target problem's native language (a graph edge, a weighted arc, a subset sum). A gadget must satisfy two properties simultaneously — completeness (a "yes" instance of the source maps to a "yes" instance of the target) and soundness (a "yes" instance of the target can be decoded back into a "yes" instance of the source). Getting both directions right, with only polynomially many gadget copies and polynomial-time construction, is the technical heart of every reduction in this article.

We build the reduction web in stages, each stage reusing structure from the previous one.

Stage 1: 3-SAT to Clique. Given a 3-CNF formula $\varphi$ with $k$ clauses $C_1, \dots, C_k$, each containing (up to) three literals, construct a graph $G$ as follows. For each clause $C_i$, create one node for each literal occurrence in that clause (so at most $3k$ nodes total, grouped into $k$ "clause groups"). Draw an edge between two nodes in different clause groups if and only if their literals are consistent — that is, they are not negations of each other (e.g., $x_3$ and $\lnot x_3$ get no edge, but $x_3$ and $x_3$, or $x_3$ and $x_7$, do get an edge). No edges are drawn within a clause group. The claim: $\varphi$ is satisfiable if and only if $G$ has a clique of size $k$.

Stage 2: Clique, Vertex Cover, Independent Set — the graph-complement triangle. These three are almost the same problem viewed from different angles. In a graph $G = (V, E)$ with $|V| = n$:

• $S \subseteq V$ is a clique iff every pair in $S$ is connected by an edge.
• $S$ is an independent set iff no pair in $S$ is connected by an edge.
• $S$ is a vertex cover iff every edge has at least one endpoint in $S$.

The identity linking independent sets and vertex covers: $S$ is an independent set of $G$ if and only if $V \setminus S$ is a vertex cover of $G$. And $S$ is a clique in $G$ if and only if $S$ is an independent set in the complement graph $\bar G$ (where edges and non-edges are swapped). These are constant-time (well, $O(n^2)$ to build $\bar G$) reductions, so Clique, Independent Set, and Vertex Cover are all NP-complete together once one of them is shown hard.

Stage 3: 3-SAT to Hamiltonian Cycle. This reduction is more intricate. For each Boolean variable $x_i$, build a variable gadget: a chain of diamond-shaped node clusters that can be traversed left-to-right or right-to-left, corresponding to setting $x_i$ true or false. For each clause $C_j$, add a clause node connected to the variable gadgets of the literals it contains, positioned so that a Hamiltonian cycle can "detour" through the clause node only if at least one of its literals is set consistently with the traversal direction chosen for that variable. Chaining all variable gadgets in sequence and attaching clause nodes as controlled side-trips produces a graph with a Hamiltonian cycle if and only if $\varphi$ is satisfiable.

Stage 4: Hamiltonian Cycle to TSP. Given a graph $G = (V, E)$ for Hamiltonian Cycle, build a complete weighted graph $K_n$ on the same vertex set: edges present in $G$ get weight 1, and all other (added) edges get weight 2. Set the budget $B = n$ (the number of vertices). Then $G$ has a Hamiltonian cycle if and only if $K_n$ has a tour of total weight $\le B$ — because any tour must use exactly $n$ edges, and it can only achieve weight $n$ if every edge used has weight 1, i.e., every edge belongs to the original graph $G$.

Stage 5: 3-SAT (or Vertex Cover) to Subset-Sum. We reduce from Vertex Cover on a graph $G=(V,E)$ with $|V|=n$, $|E|=m$, target cover size $k$. Assign each vertex $v_i$ a number and each edge $e_j$ a number, all written in base 10 (or any base $\ge 4$) with $n + m$ digits, so that different structural roles never carry over into each other's digit columns. Concretely: vertex $v_i$ contributes a 1 in digit position $i$ (from a block of $n$ vertex-columns) and a 1 in the digit position of every edge column it touches; edge $e_j$'s "filler" number contributes exactly 1 in edge-column $j$. The target sum is built so that the vertex columns must sum to exactly $k$ and each edge column must sum to exactly 2 (using vertex contributions plus filler slack digits). A subset achieving the target sum corresponds exactly to a vertex cover of size $k$. ```pseudocode // Reduction: 3-SAT --> CLIQUE function ThreeSATtoClique(phi): G = empty graph for each clause C_i in phi (i = 1..k): for each literal l in C_i: add node (i, l) to G // node tagged with clause index and literal for each pair of nodes (i, l1), (j, l2) with i != j: if l1 and l2 are not negations of each other: add edge between (i, l1) and (j, l2) return G, target_clique_size = k // Verifying direction: a clique of size k in G gives a satisfying assignment function DecodeClique(G, clique): assignment = {} for each node (i, l) in clique: var = variable_of(l) assignment[var] = true_if_positive_literal(l) return assignment // guaranteed consistent since clique has no conflicting literals ``` ```pseudocode // Reduction: VERTEX-COVER --> SUBSET-SUM (sketch) function VertexCoverToSubsetSum(G = (V, E), k): n = |V|, m = |E| base = 4 // base large enough to avoid digit carry-over for each vertex v_i in V: num[v_i] = base^i + sum( base^(n + j) for each edge e_j incident to v_i ) for each edge e_j in E: slackLow[e_j] = base^(n + j) // contributes 1 to that edge column slackHigh[e_j] = 2 base^(n + j) // contributes 2 to that edge column target = k (contribution to vertex columns, weight 1 each) + sum over edges of 2 * base^(n + j) // each edge column must total 2 S = { num[v] : v in V } union { slackLow[e], slackHigh[e] : e in E } return S, target ```

Membership in NP. Every problem discussed is in NP: a candidate solution (a satisfying assignment, a clique/cover/independent set, a Hamiltonian cycle, a tour, a subset) can be verified in polynomial time by direct inspection — checking clause satisfaction, edge membership, or an arithmetic sum, all linear or near-linear operations.

3-SAT $\le_p$ Clique — correctness. The graph has $O(3k) = O(k)$ nodes and $O(k^2)$ edges, built in $O(k^2)$ time. ($\Rightarrow$) If $\varphi$ is satisfiable, fix a satisfying assignment; in each clause at least one literal is true under it, so pick one such node per clause. Any two chosen nodes belong to different clauses and correspond to true literals under the same assignment, hence are consistent (never negations of each other), so an edge exists between them; this gives a clique of size $k$. ($\Leftarrow$) A clique of size $k$ must have exactly one node per clause group, since nodes inside one group are pairwise non-adjacent by construction. Because all pairwise chosen literals are mutually consistent (no two are negations), assigning each involved variable the truth value matching its chosen literal is a well-defined, non-contradictory partial assignment; extend arbitrarily to unmentioned variables. Every clause has its representative literal set true, so $\varphi$ is satisfied.

Clique/Vertex-Cover/Independent-Set — correctness. These follow from the two set identities stated above, each verifiable directly from the definitions of clique, independent set, and covering all edges; no gadget is even needed, just a change of viewpoint on the same graph.

3-SAT $\le_p$ Hamiltonian Cycle — correctness sketch. The variable gadgets are designed so that a Hamiltonian cycle is forced to traverse each variable's diamond chain in exactly one of two directions (this encodes a Boolean choice, and no other traversal completes a full cycle without revisiting a node). Clause nodes are attached with edges only to the literal-occurrences that would satisfy them; a clause node can be spliced into the cycle only if the corresponding variable gadget is traversed in the direction matching that literal. If $\varphi$ is satisfiable, orient each variable gadget according to the satisfying assignment and splice in every clause node via a satisfied literal — a Hamiltonian cycle results. Conversely, any Hamiltonian cycle must splice in every clause node (since every node must be visited exactly once), and the splicing point for each clause forces a genuine satisfied literal, which decodes into a satisfying assignment. The construction size is polynomial: $O(1)$ nodes per variable occurrence and $O(1)$ edges per clause.

Hamiltonian Cycle $\le_p$ TSP — correctness. Any Hamiltonian tour in $K_n$ uses exactly $n$ edges. If all $n$ edges belong to $G$ (weight 1 each), the total is exactly $n = B$. If even one edge is an added edge (weight 2), the total exceeds $n$, because the remaining $n-1$ edges contribute at least $n - 1$, giving a sum of at least $n - 1 + 2 = n+1 > B$. So a weight-$\le B$ tour exists iff a genuine Hamiltonian cycle in $G$ exists. Construction time is $O(n^2)$ to fill in the complete graph.

Vertex Cover $\le_p$ Subset-Sum — correctness. The base is chosen large enough ($\ge$ the maximum possible column sum, e.g., base $=$ max degree $+ 3$) that no carrying occurs across digit columns during any candidate summation; this makes each digit column an independent constraint. The vertex columns force exactly $k$ vertices chosen; the edge columns, each needing total exactly 2, force at least one endpoint of every edge to be among the chosen vertices (the slack numbers fill in the remainder). Decoding a valid subset sum directly yields a size-$k$ vertex cover, and vice versa. The instance size is $O((n+m)\log(\text{base}))$ bits, polynomial in the original graph's size.

Complexity honesty. These are worst-case hardness results: they say no polynomial-time algorithm solves the general problem unless P = NP, not that every instance is hard in practice. Real inputs (sparse graphs, structured formulas, small treewidth) often admit fast exact or heuristic solutions. Also, note Subset-Sum is only weakly NP-complete — it has a pseudo-polynomial time algorithm (dynamic programming in $O(nT)$ time for target sum $T$), unlike, say, 3-SAT or Clique, which are believed to have no such loophole. This distinction between weak and strong NP-completeness matters when approximation and exact algorithms are designed later.

Trace the 3-SAT $\to$ Clique reduction on a tiny formula:

Three clauses, so $k = 3$, and we seek a clique of size 3.

Edges connect nodes from different clauses whose literals are not negations of each other. For example $A_1 (x_1)$ and $B_1 (\lnot x_1)$ get no edge (direct contradiction); $A_1 (x_1)$ and $D_1 (x_1)$ get an edge (same literal, consistent); $A_2 (x_2)$ and $B_3(x_3)$ get an edge (unrelated variables, always consistent). Try the assignment $x_1 = \text{true}, x_2 = \text{true}, x_3 = \text{true}$. Check satisfaction: $C_1$: $x_1 = T$ ✓. $C_2$: $x_3 = T$ ✓. $C_3$: $x_1 = T$ ✓. So $\varphi$ is satisfiable. Decode into a clique: pick $A_1 (x_1$, true$)$ from $C_1$, $B_3 (x_3$, true$)$ from $C_2$, $D_1 (x_1$, true$)$ from $C_3$. Check all three pairs are mutually consistent (no negation pairs): $A_1$–$B_3$: $x_1$ vs $x_3$, different variables, edge exists. $A_1$–$D_1$: $x_1$ vs $x_1$, same literal, edge exists. $B_3$–$D_1$: $x_3$ vs $x_1$, different variables, edge exists. All three pairwise edges present $\Rightarrow \{A_1, B_3, D_1\}$ is a clique of size 3, matching $k=3$, confirming the correspondence. Now trace the failure direction with an inconsistent attempted clique: try $\{A_1 (x_1), B_1(\lnot x_1), D_1(x_1)\}$. Nodes $A_1$ and $B_1$ carry negated literals of $x_1$, so no edge connects them by construction — this triple is not a clique at all, illustrating why the graph correctly rejects assignments that would force $x_1$ to be both true and false.

The theory of NP-completeness crystallized in the early 1970s, transforming an informal sense that "some problems just feel harder" into a rigorous mathematical framework with a precise completeness criterion.

Recognizing a real-world problem as an instance of Vertex Cover, Independent Set, or TSP is often the single most valuable step an engineer can take, because it immediately tells them what not to try. Network security teams model minimal monitoring-node placement (to observe every communication link) as Vertex Cover. Chip design and register allocation in compilers use graph-coloring-adjacent structures related to Independent Set to decide which variables can share hardware resources. Logistics and delivery-routing systems (ride-sharing dispatch, package delivery, circuit-board drilling) confront TSP directly, and industrial solvers (like Concorde) combine branch-and-bound with the same relaxations and cutting planes that stem from understanding TSP's NP-hardness. Bioinformatics uses Clique-finding to detect groups of mutually similar protein or gene-expression profiles, and Independent Set to resolve conflicting sequence alignments. Cryptographic hardness assumptions related to Subset-Sum (the knapsack problem) motivated early public-key cryptosystems, some later broken but historically important in the field's development. Constraint-solving engines (SAT solvers) built to attack 3-SAT directly, despite worst-case exponential behavior, now scale to industrial hardware-verification and software model-checking problems with millions of variables — a striking demonstration that worst-case NP-hardness and practical solvability are not the same story. This entire landscape connects forward to Coping with NP-Hardness and Approximation Algorithms and the Approximation Ratio, where knowing a problem is NP-complete becomes the starting point for practical engineering rather than a dead end.

Ask the tutor: Can you walk me through why the Hamiltonian Cycle variable gadget forces exactly two traversal directions and not more?