NP-completeness & approximation proof drills

◈ 5 cards

The two-step NP-completeness proof template, why reduction direction matters, the classic reduction chain, and how an approximation ratio is proved against a lower bound on OPT.

The definitions you reason from

P — decision problems solvable in polynomial time.
NP — decision problems whose 'yes' answers have a polynomial-length certificate verifiable in polynomial time. (NP is about verifying a given certificate, not finding one.) $P \subseteq N P$ ; whether $P = N P$ is open.
Polynomial reduction $L_{1} \leq_{p} L_{2}$ — a poly-time computable $f$ with $x \in L_{1} ⟺ f (x) \in L_{2}$ . If $L_{2} \in P$ then $L_{1} \in P$ (solve $L_{1}$ by mapping to $L_{2}$ ). Reductions are transitive.
NP-hard — every problem in NP reduces to it (at least as hard as all of NP). NP-complete — NP-hard and in NP.

The two-step template to prove a problem X is NP-complete

This is a near-guaranteed exam question. Always exactly two steps:

Show $X \in N P$ — describe a certificate and a poly-time verifier. (e.g. for VERTEX-COVER: the certificate is the vertex set; verify its size ≤ k and that it covers every edge — O(V+E).)
Show $X$ is NP-hard — pick a known NP-complete problem $Y$ and give a poly-time reduction $Y \leq_{p} X$ . Prove $f$ runs in poly time and the equivalence $y \in Y ⟺ f (y) \in X$ (both directions).

Reduction DIRECTION — the mistake that loses the marks

You reduce FROM the known-hard problem TO your new problem: $Y \leq_{p} X$ with $Y$ known NP-complete. This shows $X$ is at least as hard as $Y$ . Reducing the other way ( $X \leq_{p} Y$ ) proves nothing about $X$ 's hardness — it would only show $X$ is no harder than $Y$ . Mnemonic: to prove X is hard, hide a hard problem inside X.

The reduction chain (know the map)

$CIRCUIT-SAT \to SAT \to 3-CNF-SAT \to {CLIQUE \to VERTEX-COVER \to HAM-CYCLE \to TSP SUBSET-SUM$

CIRCUIT-SAT is NP-complete from first principles (Cook–Levin); everything else is proved NP-complete by a reduction from a problem to its left. When asked to prove a new problem NP-complete, reduce from whichever of these is structurally closest (3-CNF-SAT for logic/assignment problems, VERTEX-COVER/CLIQUE for graph problems, SUBSET-SUM for number/partition problems).

Approximation: prove a ratio against a LOWER BOUND on OPT

When a problem is NP-hard, settle for a solution provably within a factor $ρ$ of optimal. The trick in every ratio proof: you cannot compute OPT, so bound OPT from below by something you can measure, then compare your algorithm's output to that bound.

Vertex cover 2-approximation — repeatedly pick an uncovered edge and take both endpoints. The picked edges form a matching (no two share a vertex), and any vertex cover must include ≥ one endpoint of each — so $∣ O P T ∣ \geq$ (#picked edges), while the algorithm uses $2 \times$ that. Ratio $\leq 2$ .
Metric TSP 2-approximation — a preorder walk of an MST; the triangle inequality bounds shortcuts, and $MST \leq OPT tour$ . Ratio $\leq 2$ . General TSP has no constant-factor approximation unless P = NP — the triangle inequality is exactly what rescues the metric case.
Definitions: a PTAS achieves $1 + ε$ for any fixed $ε$ (time poly in n); an FPTAS is also poly in $1/ ε$ (e.g. subset-sum by trimming).

Work top to bottom. Step 3 is where the direction error costs the marks.