optional · interactive figures

Explore: the oracle and a certificate

Watch brute force walk through every candidate of the running example, then build a cover and a matching yourself and see when they prove each other optimal.

optional: nothing in the lab depends on itback to the slides

00 · explore

The oracle, candidate by candidate

Try: step through all 16; watch "best so far" change only once. Static versions: the running example, brute force.

00 · explore

Build a certificate

Try: on the running example, find a cover and a matching of the same size; then try the same on the triangle. Static versions: checked step by step, the triangle.

What it shows. The two halves of a certificate for vertex cover, checked as you build them: a cover $C$ gives an upper bound, a matching $M$ a lower bound, and equal sizes prove both optimal. All checks are computed in the page from the edge lists written in this file.

Running example: $C = \{1, 2\}$ and $M = \{01, 23\}$ close the gap at 2.
Triangle: every matching has one edge and every cover two vertices, so the sizes can't meet; the verdict stays "between 1 and 2".
Path on four vertices: the slide "A lower bound for vertex cover".
Spider: the middle row is a cover of size 3 and the three legs a matching of size 3, the certificate from "The harness catches what you believe". Try greedy's cover (centre first, then one vertex per leg) and see it can't be matched.