Always a combinatorial problem you have never seen before. They give you a reduction from 3SAT or Vertex Cover. The reduction is always intentionally broken. Same 5 sub-parts every time:
| Part | Task | Pts | What to do |
|---|---|---|---|
| (a) | Prove in NP | 2 | Certificate + poly-time verifier |
| (b) | Source instance | 1 | Small yes-instance of 3SAT or VC (from scratch) |
| (c) | Apply reduction | 2–3 | Follow given reduction step by step on your instance |
| (d) | Check result | 1 | Is f(I) a yes-instance? Usually no — this reveals the break |
| (e) | Fix reduction | 1–2 | Identify which direction fails, propose correction |
Memorize this structure — 2 free points every exam
Certificate: [the thing you're searching for]
e.g., "a subset S' ⊆ S", "a function f: B → {r,t}", "an edge set E' ⊆ E"
Verifier: given the certificate, check:
1. [structural constraint] — in O(...)
2. [value/size constraint] — in O(...)
3. [connectivity/coverage] — in O(...)
All checks polynomial in |input|. ∴ Problem ∈ NP. □
Tips:
Part (b) asks you to construct a small yes-instance from scratch. You must know these definitions cold.
3SAT
Definition: Given variables U and clauses C where each clause has exactly 3 literals, is there a truth assignment to U satisfying all clauses?
Go-to instance (|U|=4, |C|=2):
Why this one works: p appears positive in C1 and negated in C2; r appears negated in C1 and positive in C2. Variables appear in mixed polarity — makes it a realistic instance that exercises the reduction.
Vertex Cover
Definition: Given graph G = (V, E) and integer K, can you pick ≤ K vertices such that every edge has at least one endpoint in the set?
A vertex cover is a set S ⊆ V such that for every edge {u, v} ∈ E, at least one of u or v is in S. You are “covering” edges by picking their endpoints.
Go-to instance (|V|=4, |E|=4, K=2):
Verify: {v1,v2} — v2∈S ✓. {v2,v3} — both ∈S ✓. {v3,v4} — v3∈S ✓. {v1,v3} — v3∈S ✓. Every edge covered.
How the break always works
A correct reduction must preserve answers in both directions:
The exam reduction always breaks one direction. Most commonly:
Common fixes:
The exam says “no need for a full proof” — 1–2 sentences explaining the fix is sufficient.
| Exam | Problem | Source | Reduction type |
|---|---|---|---|
| Endterm 24–25 | AUCTION (subset sum variant) | 3SAT | Table-based (variable/clause membership → decimal values) |
| Resit 24–25 | GRAPHICAL STEINER TREE | Vertex Cover | Graph-based (edge-splitting + hub node) |
| Endterm 23–24 | TRAITORS (assign r/t roles) | 3SAT | Set-based (literals + z/¬z → groups) |
| Resit 23–24 | SKILL-CIRCUIT (DAG from skill graph) | Vertex Cover | Graph-based |
Instance: Set of items S, value function v: S → ℕ, target t ∈ ℕ.
Question: Is there S′ ⊆ S such that Σx∈S′ v(x) = t?
Source NPC problem: 3SAT
Certificate: the subset S′ ⊆ S.
Verifier:
All polynomial. □
U = {p, q, r, s}, C = {(p ∨ ¬q ∨ ¬r), (r ∨ s ∨ ¬p)}
Yes-instance: p=T, q=F, r=T, s=T satisfies both clauses.
Mixed polarity: p is positive in C1, negated in C2; r is negated in C1, positive in C2.
Step 1 — Build item set
S = U ∪ {¬u | u ∈ U} = {p, q, r, s, ¬p, ¬q, ¬r, ¬s}
Step 2 — Build value table
Columns: one per variable (1 if item matches that variable), one per clause (1 if literal appears in that clause). Value = row read as a decimal number.
| Item | p | q | r | s | C1 | C2 | v(item) |
|---|---|---|---|---|---|---|---|
| p | 1 | 0 | 0 | 0 | 1 | 0 | 100010 |
| q | 0 | 1 | 0 | 0 | 0 | 0 | 010000 |
| r | 0 | 0 | 1 | 0 | 0 | 1 | 001001 |
| s | 0 | 0 | 0 | 1 | 0 | 1 | 000101 |
| ¬p | 1 | 0 | 0 | 0 | 0 | 1 | 100001 |
| ¬q | 0 | 1 | 0 | 0 | 1 | 0 | 010010 |
| ¬r | 0 | 0 | 1 | 0 | 1 | 0 | 001010 |
| ¬s | 0 | 0 | 0 | 1 | 0 | 0 | 000100 |
Step 3 — Compute target
t = |U| ones followed by |C| threes = 111133
Logic: pick exactly one of {u, ¬u} per variable → each variable column sums to 1. Each clause has 3 literals → target of 3 per clause column.
No.
The satisfying assignment p=T, q=F, r=T, s=T selects items {p, ¬q, r, s}:
100010 + 010010 + 001001 + 000101 = 111122 ≠ 111133
The variable columns sum to 1 (correct), but the clause columns sum to only 2 (need 3). Picking one literal per variable can contribute at most 1 per clause — and there are only 4 variables covering 6 clause slots (2 clauses × 3 literals). The target of 3 per clause is unreachable.
The break: No ↛ No direction fails. A correct assignment picks one literal per variable but can never sum to exactly 3 in every clause column, so even satisfiable formulas map to no-instances of AUCTION.
Fix option 1: Change the target from 3 to 1 in clause columns (t = 111111). Then at least one true literal per clause is sufficient — which is exactly what satisfiability requires.
Fix option 2: Add padding items for each clause that contribute only to that clause’s column, allowing the sum to reach exactly 3 regardless of how many true literals appear.
Instance: Undirected graph G=(V,E), vertex subset X ⊆ V, integer K.
Question: Is there E′ ⊆ E with |E′| ≤ K such that all vertices in X are connected in (V, E′)?
Source NPC problem: Vertex Cover
Certificate: the edge subset E′ ⊆ E.
Verifier:
All polynomial. □
V = {v1, v2, v3, v4}, E = {{v1,v2}, {v2,v3}, {v3,v4}, {v1,v3}}, K = 2
Yes-instance: Cover = {v2, v3}.
Check: {v1,v2}—v2✓, {v2,v3}—both✓, {v3,v4}—v3✓, {v1,v3}—v3✓. Every edge has at least one endpoint in the cover.
Step 1 — Number the original edges
e1={v1,v2}, e2={v2,v3}, e3={v3,v4}, e4={v1,v3}
Step 2 — Split each edge with a middle vertex
Create W = {w1, w2, w3, w4} (one per edge). Replace each edge ei={u,v} with two edges {u, wi} and {wi, v}.
Esplit = {{v1,w1}, {w1,v2}, {v2,w2}, {w2,v3}, {v3,w3}, {w3,v4}, {v1,w4}, {w4,v3}}
Step 3 — Add hub vertex s connected to all original vertices
Ehub = {{v1,s}, {v2,s}, {v3,s}, {v4,s}}
Step 4 — Assemble the Steiner Tree instance
V′ = V ∪ W ∪ {s} = {v1, v2, v3, v4, w1, w2, w3, w4, s}
E′ = Esplit ∪ Ehub (12 edges total)
X = {s} ∪ W = {s, w1, w2, w3, w4} (must all be connected)
K′ = K = 2
No.
We need s, w1, w2, w3, w4 all connected. Each wi is only reachable via its two endpoint vertices (e.g., w1 is only adjacent to v1 and v2). Reaching any single wi from s takes at least 2 edges (s→v→w). Connecting all 4 w-vertices requires far more than K′=2 edges.
The break: Yes ↛ Yes direction fails. K′=K is far too small — even when a vertex cover of size K exists, connecting the Steiner Tree requires many more edges.
Fix: Set K′ = K + |E|. Intuition: a vertex cover of size K selects K vertices; connecting them to s costs K edges (one {v,s} per cover vertex). Each original edge is covered, so its w-vertex is reachable via 1 edge through the covering endpoint — that’s |E| additional edges. Total: K + |E|. This makes both directions of the reduction hold.
Problem: Given contestants B and groups S = {S1,...,Sn} with Si ⊆ B, is there f: B → {r, t} such that each Si has at least one r and one t?
Source: 3SAT.
(a) Prove TRAITORS ∈ NP.
(b) Give a 3SAT instance with |U|=4, |C|=2.
(c) Apply reduction: B = U ∪ {z, ¬z} ∪ {¬u | u ∈ U}, S = {c ∪ {z} | c ∈ C}.
(d) Is it a yes-instance?
(e) Fix the reduction.
(a) Certificate: function f: B → {r, t}. Verifier: check f maps to {r, t} in O(|B|), check each Si has at least one r and one t in O(|S| × |B|). All polynomial. □
(b) U = {p, q, r, s}, C = {(p ∨ ¬q ∨ ¬r), (r ∨ s ∨ ¬p)}. Satisfied by p=T, q=F, r=T, s=T.
(c) B = {p, q, r, s, ¬p, ¬q, ¬r, ¬s, z, ¬z}. S = {{p, ¬q, ¬r, z}, {r, s, ¬p, z}}.
(d) Yes — assign f(p)=t, f(r)=t, all others=r. S1 = {p(t), ¬q(r), ¬r(r), z(r)} has both. S2 = {r(t), s(r), ¬p(r), z(r)} has both. The break is in the No→No direction — this particular yes-instance works fine.
(e) The flaw: when the 3SAT formula is unsatisfiable, TRAITORS may still have a solution because z is a free variable — it can be assigned r or t independently of any literal. Groups contain positive/negated literals plus z, so z provides a free role assignment that can rescue otherwise broken groups. Fix: for each variable u, add a consistency group {u, ¬u, ¬z} that forces the variable assignments and z to be coupled, preventing spurious solutions.
Problem: Given directed graph G=(V,E), colors c: V → {1,...,k}, vertices s, t. Is there a path from s to t that uses each color exactly once?
(a) Prove COLORFUL PATH ∈ NP.
(b) Give a 3SAT instance with |U|=3, |C|=2.
(c)–(e) Left as thinking exercise.
(a) Certificate: the path P = (v1, ..., vk). Verifier: check each consecutive pair (vi, vi+1) ∈ E in O(k), check v1=s and vk=t, check each color appears exactly once in O(k). All polynomial. □
(b) U = {x, y, z}, C = {(x ∨ y ∨ ¬z), (¬x ∨ z ∨ y)}. Satisfied by x=T, y=T, z=F.