One algorithm, three numbers. On the five-cycle the 2-approximation for vertex cover realises 4/3. Over every one of the 63 non-empty graphs on four vertices, each solved exactly, the worst it realises is 2. And over every graph of every size the proof gives at most 2. Three statements of increasing strength, and only the last is a theorem — which is the hazard this Subject was built around, met one last time where it matters most.
Core ideas
The first idea is the ladder of three claims and what separates each rung from the next. The second is a subtlety about what an exhaustive sweep is a sweep over. The third is the close: what the six strategies have in common.
A ratio measured on the graph in the box is a fact about that graph. A sweep over every graph of a size is a much stronger fact — it is a genuine universal statement, quantified over a finite set that has been exhausted. A bound over every size is stronger again and no enumeration can reach it, because there are infinitely many sizes. The first gap is closed by computing more; the second cannot be closed by computing at all.
The panel says this itself, and it is the subtlety that makes the third rung necessary rather than merely tidier. The matching is built greedily in edge order, so the worst ratio the sweep finds is the worst case of this matching routine on graphs of that size; a different edge order gives a different matching and possibly a different ratio. The proof never mentioned the order, so the bound of 2 covers every implementation at once, including ones nobody has written.
Prune an exact search; parameterise the exponential; approximate with a guarantee; approximate under a hypothesis; buy accuracy by the epsilon; or restrict to a tractable special case. Each gives something up, and every one of them is defended the same way: a quantity the algorithm can compute, compared against a claim that quantifies over inputs. The measurement says what happened; the proof says what can happen. Neither is a substitute for the other, and this course has printed them side by side on every page.
The material
The measured ratio, the exhaustive sweep, the proved bound, what separates them, and the six responses this course built.
The graph is the five-cycle. The maximal matching takes two edges, the cover takes their four endpoints, the optimum is three, and the realised ratio is 4/3 against a promise of 2. Everything about that sentence is measured except the promise.
The middle row is the one this library can rarely produce, and it is worth being clear about how strong it is. It is not a sample. Every non-empty graph on four vertices is examined — there are 2^6 - 1 = 63 of them, one per non-empty subset of the six possible edges — and each is solved exactly by enumerating subsets of its vertices. So it is a universal statement over a finite domain, and 49 of the 63 attain the worst ratio of 2.
It still is not the theorem. Five vertices gives 1023 graphs and the worst ratio is again 2; three vertices gives 7 and the answer is again 2. Three sizes, three exhaustive answers, all equal to the proved bound — and the bound holds for sizes no enumeration will ever reach, for a reason that has nothing to do with any of the three counts: the matched edges are disjoint, so any cover needs a vertex from each, and the algorithm takes exactly two per edge.
A bound is tight when some instance attains it, so the constant cannot be lowered without changing the algorithm. The sweep is how this page establishes tightness: it produces the attaining instances rather than asserting that they exist, and it reports both the first in edge order — a single edge — and the densest, which on four vertices has five edges.
Reporting both witnesses is not fussiness. A reader shown only the single edge concludes that the factor of 2 is an artefact of a degenerate case and that real graphs are fine. The five-edge witness on four vertices, and the seven-edge witness at five vertices, say otherwise: the worst case lives among dense graphs too.
Every page here has put a measured quantity beside a claim the measurement cannot establish, and said which is which. The reductions measured the map on solutions and proved the equivalence of answers. Branch and bound measured node counts and proved only that the bound cannot cut the optimum. The parameterised search measured nodes and printed 2^k · n beside 2^n as expressions. The four guarantees each measured a realised ratio and printed the promise beside it, and never a ratio without the optimum it was a ratio to.
The path ends here, and the position is worth stating plainly. Data structures paid for the operations everything else spends; sorting made the analysis probabilistic; graphs supplied the algorithms that certify their own answers; greedy methods and dynamic programming are two answers to one question about optimal substructure; strings, geometry and randomisation applied all of it to one world each. This course needed every one of them — the probabilistic method, subset sum's table, König's theorem and both proof templates — because an approximation ratio is a stays-ahead argument against a lower bound, and a reduction is a construction you have to be able to build.
And the discipline that ran through all of it is the sentence in the footer of every page: a count is measured by running the algorithm on the input shown, and a count on one input is not a bound. This page adds the only refinement it ever needed. A count on every input of one size is not a bound either. It is a great deal better than one count, it is the strongest thing a computer can hand you, and it is still not a quantifier over all sizes. That last step is the one you take with a proof, and it is why every lab on this path has a theorem printed next to it.
Interactive
The matched edges share no vertex, so the optimum is above the matching; the cover is twice it — and the optimum appears only in the last line
Method
Four questions, in this order, for every number a lab hands you.
One instance, every instance of a size, or every instance? The three are different kinds of claim and they are printed in the same typeface. The panel here labels its rows “one graph”, “63 graphs” and “every graph, of every size” for exactly this reason.
A ratio without the quantity it is a ratio to is not a measurement. If the optimum is not on the page, the fraction above it has an invented denominator, and no arrangement of the other numbers repairs that.
A node count was counted. 2^k · n, H_n and ε · OPT are expressions evaluated at this instance's numbers. Both belong on the page and they answer different questions, and a sentence mixing them is a sentence about nothing.
Move the slider, switch the preset, break the hypothesis. A measurement that survives every instance you can reach is worth having and is not a bound; a measurement that changes when you move one control was never more than a fact about one input. Either way, the thing that settles the general claim is the proof beside it.
The graph in the box is 1-2, 2-3, 3-4, 4-5, 5-1. The sweep below is over every graph on four vertices and does not depend on it.
The five-cycle's chain has slack in exactly one place: the matching is 2 and the optimum is 3, so the cover of 4 comes in under the promise of 4 only because twice the matching happens to equal it. An odd cycle cannot be covered by a perfect matching's endpoints, and that is where the 4/3 rather than 2 comes from.
Three exhaustive sweeps at three sizes all return 2, which is as much agreement between measurement and proof as this library can produce. It is worth enjoying and it is worth being precise about: the proof would still be the only reason to believe the bound at six vertices, and the slider stops at five — six vertices would be 32767 graphs to solve exactly.
For a faded rehearsal, and as the last exercise on this path: predict the worst ratio at three vertices before moving the slider, and then say what you would have to do to establish it at a hundred. The supplied first move: a single edge is a graph at every size and realises exactly 2, so the worst ratio is at least 2 at every size, and the proof says it is at most 2. Write down which of those two facts a computer gave you.
You should be able to distinguish a ratio measured on one instance, a worst case found by exhausting a finite family, and a bound proved over all instances; name the denominator every ratio needs; separate a counted quantity from an evaluated expression; and state which of the six responses to a hard problem keeps exactness and what each of the others gives up.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.