`, ends with ``, exactly one JS marker, `selfcheck()` returns true over all 1088 graphs on ≤5 vertices, tamper is caught, real DOI source, footer signature correct. THE APPROXIMATION ALGORITHM · WORLD II — THE FOLD · THE OCHO
◄ WORLD II · THE FOLDTHE OCHO · blue builds │ the machine │ red breaks

THE APPROXIMATION ALGORITHM

When you cannot solve it exactly in reasonable time, bound how far off you are. David S. Johnson's answer to intractability: a fast algorithm with a proven worst-case ratio. Down the center, data flows: a graph goes in, the greedy 2-approximation for VERTEX-COVER picks an uncovered edge and takes both endpoints, and a cover comes out — never more than 2× the brute-force optimum. The blue team proves that bound; the red team tries to break it.

source D. S. Johnson, Approximation Algorithms for Combinatorial Problems, J. Comput. Syst. Sci. 9(3):256–278 (1974) — doi.org/10.1016/S0022-0000(74)80044-9. Rendered, not quoted.

◧ blue team · builds & defends
3

THE MODEL — greedy & the matching bound

The algorithm. While an uncovered edge remains, pick one — say (u,v) — put both u and v in the cover, and mark every edge touching u or v as covered. Repeat. The picked edges form a matching M (no two share a vertex).

Why ≤ 2× optimum. Any cover must include at least one endpoint of every edge in M. Because M's edges are vertex-disjoint, that is |M| distinct vertices — so OPT ≥ |M|. Greedy returns exactly 2|M| vertices. Hence greedy ≤ 2·OPT. The matching is both the algorithm and its own lower bound.

For the current graph, live:

5

THE LINEAGE — the reply to NP-hardness AVAN

Minimum vertex-cover is NP-complete — one of Karp's original 21. Where the-np-completeness proves no poly-time algorithm finds the exact optimum (unless P=NP), this sphere is the constructive reply: a poly-time algorithm that misses by a bounded, proven factor.

That is the trade — optimality for tractability, with a certificate. The neighbour forbids the exact answer; this one ships a guaranteed-close answer instead. Each sphere is the next one's premise.

7

THE WITNESS live

The blue team's live check: re-run greedy over every graph on 4 vertices (all 64) and confirm each output is a valid cover with size ≤ 2·OPT. If red tampers, this badge is where it shows.

▼ the machine ▼
4

DATA IN — a graph in ↓

The input is a graph: a set of vertices and a set of edges joining them. A vertex cover is a set of vertices that touches every edge — pick vertices so no edge is left bare. The minimum cover is what we want; finding it exactly is NP-hard.

Choose a graph below; its edges are fed to the engine. Small enough that brute force can still find the true optimum for comparison — that is the whole honesty of this instrument.

▼   feed the graph into the engine   ▼
0

▣ THE PANEL — the engine LIT

Purple = chosen by greedy. Thick purple edge = a matching edge (both endpoints taken). Change the graph — the cover is recomputed on the spot, never looked up.

▼   the engine emits a cover + a ratio   ▼
8

DATA OUT — the result out ↓

What the machine produces, proven: over every graph on up to 5 vertices (all 1088 of them) greedy returns a valid cover of size ≤ 2·OPT — ratio ≤ 2 without exception. And the bound is tight: a single edge (or any perfect matching) forces exactly 2×. The current graph's cover, size, optimum and ratio are above; the guarantee is the output.

The blue team's witness (left) confirms this live; the red team (right) tries to make the cover invalid.

red team · attacks & breaks ◨
1

THE ADVERSARY

WALL The factor 2 is not a stepping stone to 1. Vertex-cover is APX-hard: no poly-time scheme gets arbitrarily close. It cannot be approximated below 1.3606 unless P=NP (Dinur–Safra), and under the Unique Games Conjecture 2−ε is itself hard (Khot–Regev). So this simple 2 may be near the wall, not a first draft.

A guarantee is worst-case, not typical: on real inputs greedy is often much better than 2, and on the graphs above it is often 1. The ratio bounds the promise, not the usual result — a bound can be loose and still be the best proven.

2

THE GRAVEYARD

"Just repeatedly grab the highest-degree vertex — that's the 2-approx." Cut. Greedy-by-degree for cover is the Θ(log n) algorithm, not 2. The 2-bound needs the edge/matching rule: take both endpoints.

"This exact vertex-cover algorithm is Johnson 1974." Corrected. AMBER The maximal-matching 2-approx is folklore (Gavril / Yannakakis, in Garey & Johnson 1979). Johnson 1974 founded the field — the greedy ln n bound for set cover and the ratio framework this lives in.

"2-approximation means the answer is always twice the optimum." Cut. 2 is an upper bound. It is hit exactly only on specific graphs (a bare edge); on a triangle greedy is optimal.

6

THE TAMPER — break it

The red team's move: take only one endpoint of each picked edge instead of both. The cover shrinks — but it is no longer a cover: some edge is left bare. The blue team's witness (window 7) is watching.

Drop the second endpoint and greedy still runs in poly time — but on some graph an edge whose only cover-vertex was the dropped endpoint goes uncovered. The witness recomputes over all 64 four-vertex graphs, finds invalid covers, and turns red. Nothing is faked; the attack is real and it is caught.