GTOIgraph theory, redesigned

Chapter 9 · Hardness and Escape Routes

P, NP, and Reductions — What You Actually Need

The definitions in contest language, how a reduction is written, and what "NP-complete" does and does not forbid.

  • core
  • complexity
  • reductions
Read first
Definition
  • **P**: decidable in time polynomial in the input length.
  • NP: every yes instance has a certificate verifiable in polynomial time. (Vertex cover: the certificate is the set itself; check size and coverage in O(n+m).)
  • NP-complete: in NP, and every NP problem reduces to it. If any NP-complete problem is in P, then P = NP.
NoteWhat the definition does not say

It does not say a problem is slow for the given n. "Vertex cover with n ≤ 20" is trivial; "with n ≤ 105 and the graph is a tree" is a 6-line DP (Trees: Six Definitions of One Object). NP-completeness is a statement about uniform algorithms across all inputs. A contest problem is never "solve NP-complete instances fast" — it is "solve this NP-complete problem under a promise, or exactly because n is small, or approximately".

#Reductions, mechanically

To show B is NP-hard: pick a known NP-complete A, and give a polynomial map f with

x ∈ A ⇔ f(x) ∈ B .

Direction matters: you reduce the known-hard problem to the new one. Then a fast algorithm for B would give one for A.

ExampleIndependent set ⇄ vertex cover (the cleanest pair)

S is an independent set ⇔ V ∖ S is a vertex cover. So α(G) + τ(G) = n, and an algorithm for either solves the other with the same running time — a reduction that is one line and also a theorem. Note it converts maximisation to minimisation, which is why the "minimum" version is the one usually stated as complete.

Example3-SAT → 2-SAT is impossible (unless P = NP), and what you can do instead

A reduction must keep the problem class: 2-SAT is in P (2-SAT), so no polynomial reduction from 3-SAT to it exists unless P = NP. If a problem looks like 3-SAT but each variable appears in at most 2 clauses, that is a promise you can exploit: the constraint graph has max degree 2, so it is paths and cycles and can be solved by DP — the typical shape of a "3-SAT that is actually easy" problem.

Four habits that make reduction-writing fast

  1. Prove membership in NP first: if you cannot state the certificate, you are aiming at the wrong class (NP-hard vs FP vs search),
  2. choose the source problem by structure match: numbers → Subset Sum / Partition; sets and conflicts → Independent Set / Clique; assignment → 3-SAT; ordering → Betweenness; partition into groups → 3-D Matching,
  3. keep the construction local: gadgets of constant size, with the "iff" checked in both directions for each gadget,
  4. finish by stating what the reduction forbids: "hence no polynomial exact algorithm unless P = NP" — and then immediately ask which escape route the constraints suggest (Escape Routes: What To Do When It Is NP-Hard).
Watch outTwo confusions that cost real points
  • NP-hard vs NP-complete: optimisation versions (minimum vertex cover) are NP-hard but not decision problems, so they are not "NP-complete" strictly speaking. Say "NP-hard" and be safe.
  • decision vs search: a decision oracle for "τ(G) ≤ k?" gives the actual set with n extra queries (binary search then greedy inclusion), so algorithmically the two are equivalent up to a factor n. Knowing this saves you from "but my problem asks for the set" panic.
ExerciseThree reductions to write out in full
  1. Clique ≤m Independent Set via the complement graph — state the gadget and both directions of the equivalence.
  2. Explain why the identity α(G) + τ(G) = n turns a maximisation into a minimisation, and why the analogous statement for matchings (ν(G) ≤ τ(G), with equality only for bipartite graphs per Kőnig's Theorem and Minimum Covers) gives you an algorithm on bipartite graphs but not on general ones.
  3. Subset Sum ≤m "partition a tree's edge weights so both halves have equal sum" — build the tree as a star and note what the reduction costs in bits.