Lesson · Intractability and Approximation · Guarantees, and the lower bound they rest on

Twice a Matching

A guarantee cannot be a claim about the optimum, because nobody computing it knows the optimum. It is a claim about a lower bound the algorithm can see. A maximal matching is such a bound: its edges share no vertex, so any cover needs a distinct vertex for each, and taking both ends of each is a cover of exactly twice that. On the loaded graph the ratio is exactly 2, and the panel then searches every graph on four vertices to see whether anything does worse.

Open the interactive lesson Practice

matching ≤ optimum ≤ cover = 2 × matching the whole proof, four numbers the optimum appears in the middle link and nowhere in the algorithm three disjoint edges: matching 3, optimum 3, cover 6, ratio exactly 2 worst ratio over all 63 graphs on four vertices with an edge: 2 on a bipartite graph the exact answer is a maximum matching — König, and cheap

The chain of four numbers, and the one link that mentions the optimum

Core ideas

What this lesson establishes

The first idea is what a ratio is a ratio to, and where the guarantee's evidence actually comes from. The second is the chain, which is the proof written as four comparisons. The third is the special case where none of this is needed.

A guarantee is proved against a lower bound, not against the optimum

Say an algorithm returns a cover at most twice the smallest. The smallest is not known — computing it is the problem. What is known is the matching the algorithm built, and the argument runs entirely through it: the matching is below the optimum, and the answer is exactly twice the matching. The optimum is squeezed in the middle and is never computed. That is the shape of every approximation guarantee on this course, and it is why the panel draws four numbers on one axis rather than two.

Why both ends, and why maximal is enough

Take edges one at a time, skipping any that touches a vertex already used: that is a maximal matching, meaning no edge can be added, not a maximum one. Maximal is enough for both halves. Its edges are disjoint, so every cover needs a vertex from each and the optimum is at least its size; and if some edge had neither end in the chosen set, that edge could have been added, contradicting maximality — so taking both ends of every matched edge covers everything.

Bipartite graphs do not need this at all

König's theorem, proved from max-flow in the graph course, says the minimum vertex cover of a bipartite graph equals its maximum matching, and both are computable in polynomial time. The graph on screen is bipartite: three disjoint edges, maximum matching 3, minimum cover 3. So the approximation returns 6 where an exact polynomial algorithm returns 3, and this instance — where the guarantee is exactly attained — is an instance where the guarantee should not have been used. Knowing which special cases are exactly solvable is part of knowing when to approximate.

The material

The algorithm, the chain it rests on, and the sweep that tests the promise

The two-line algorithm, the four-link chain, the measured ratio, the search over every graph of a size, and the special case where the exact answer is cheap.

Definition · Maximal matching, and the cover built from it

A matching is a set of edges no two of which share a vertex; it is maximal when no further edge can be added. The algorithm scans the edges in order, keeps an edge whenever neither end has been used, and returns the set of all endpoints of the kept edges as its cover.

Theorem · The endpoints of a maximal matching are a cover of at most twice the minimum

Let M be a maximal matching and C the set of endpoints of its edges. Then C is a vertex cover, and |C| = 2|M| ≤ 2 · τ, where τ is the size of the smallest cover.

C is a cover: if some edge had neither end in C, neither of its ends is used by a matched edge, so it could be added to M, contradicting maximality.

|M| ≤ τ: the edges of M are pairwise disjoint, and any cover must contain at least one end of each, so it contains at least |M| distinct vertices.

|C| = 2|M| by construction, since the endpoints of disjoint edges are all different. Combining, |C| = 2|M| ≤ 2τ. Note which quantities appear in each line: the algorithm computes M and C, and τ enters only in the middle inequality, which is the one nobody has to evaluate.

□

The chain, as four numbers on the panel

matching 3 a lower bound the algorithm can see optimum 3 by exhaustive search over the subsets cover built 6 the endpoints of the matching twice the matching 6 the promise

The loaded graph is the three disjoint edges 1-2, 3-4, 5-6. The matching takes all three, the cover takes all six vertices, and the optimum is 3 — one end of each edge. The realised ratio is exactly 2 and the panel prints it against the promised 2. This is the worst the algorithm can do, and it is not an artefact of a strange graph: every matched edge needs one vertex in a cover and the algorithm takes two.

The middle link is the only one needing an optimum, and it is the only one the panel had to do extra work for: 3 comes from an exhaustive search over the subsets of the vertices. Without it the ratio printed above would be a fraction with an invented denominator, which is why every mode of this lab computes both halves.

Every graph of a size, not just this one

The panel then does something a page about approximation usually only describes. It enumerates every graph on the number of vertices its slider names — 63 non-empty graphs on four vertices — solves each one exactly, runs the approximation on each, and reports the worst ratio any of them produced. The answer is 2, attained by 49 of the 63, and it names both the first witness in edge order, which is a single edge, and the densest, which has five edges. Both, because a reader shown only a single edge concludes the bound is an artefact of a degenerate case.

Example · A ratio strictly inside the promise

Switch to the five-cycle: the greedy matching takes two edges, the cover has four vertices, the optimum is three, and the ratio is 4/3. Switch to the two triangles and the ratio is 1 — the algorithm returns the optimum. Neither number is the algorithm's number, and both are inside a promise of 2 that the first graph attains exactly.

One honest caveat the panel states itself. The matching is greedy in edge order, so the worst ratio found by the sweep is the worst case of this implementation on graphs of that size; a different edge order is a different matching. The bound of 2 covers all of them, because the proof never mentioned the order — which is the sense in which a proof is stronger than a sweep over every instance of a size.

Interactive

Vertex cover in two: a matching is the lower bound

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

Edit the graph, then search every graph of a size for the worst ratio

The optimum is an exhaustive search over the subsets, computed separately from the algorithm, so the realised ratio has a real denominator. The second table goes further and enumerates every graph on the number of vertices you choose, which turns “the bound is tight” from a word into an instance.

Worked example

Edges, as u-v

Search every graph on this many vertices4

Vertices and edges—

Matching found, the lower bound—

Cover the algorithm built—

The optimum, by exhaustive search—

The ratio it realised—

Within the promised 2—

Worst ratio over every graph of that size—

A graph that attains it—

Take edges one at a time, skipping any that touches a vertex already used: that is a maximal matching. Every one of its edges needs at least one endpoint in any cover, and its edges share no vertex, so the optimum is at least the matching size. Taking both ends of every matched edge covers the whole graph, because an uncovered edge would have been addable to the matching. So the cover is at most twice a number that is at most the optimum — and neither half of that sentence mentions the optimum itself.

Method

Stating and checking an approximation guarantee

Five steps, and the first is the one that decides whether the guarantee means anything.

Find a lower bound the algorithm can compute

Not the optimum — something below it that falls out of the run. A maximal matching is the example here; a minimum spanning tree is the example on the next page. If there is no computable lower bound, there is no guarantee to prove, only a hope to measure.

Bound the answer against that lower bound

Show the returned solution is at most ρ times the lower bound, by construction rather than by argument if possible. Here it is exactly twice, because the cover is the endpoints of disjoint edges and nothing else.

Write the chain out and check which link needs the optimum

Lower bound, optimum, answer, promise. Only the middle inequality involves the optimum, and it holds because the lower bound is a lower bound. If your chain needs the optimum anywhere else, the guarantee is not provable in this shape.

Print the realised ratio with the optimum it is a ratio to

On instances small enough to solve exactly, compute the optimum and divide. A ratio without its denominator is not a measurement, and the panel refuses to show one. Say also that the realised ratio is about this instance and the promise is about all of them.

Check the special cases before approximating at all

Bipartite graphs have an exact polynomial algorithm for this problem, and the graph on screen is bipartite. Trees, bipartite graphs and bounded-degree graphs are the usual islands of tractability; walking past one to use a 2-approximation is a real mistake and the panel's default instance is an example of it.

Ratios, lower bounds and special cases

Score 0 / 0

Choose the answer you can justify.

Three disjoint edges, and the sweep over every graph on four vertices

The graph is 1-2, 3-4, 5-6. The matching is greedy in edge order and takes every edge, since none of them touch. The sweep below is a separate computation and does not depend on the graph in the box.

the link in the chain value why it holds matching ≤ optimum 3 ≤ 3 disjoint edges need distinct vertices optimum ≤ cover 3 ≤ 6 the optimum is the smallest cover cover = 2 × matching 6 = 2 × 3 both ends of each matched edge so cover ≤ 2 × optimum 6 ≤ 6 the three lines above, in that order realised ratio 6 / 3 = 2 against the promised 2 the cover is a cover checked against the edge list the claim, and what it is about result the ratio on the graph on screen one graph 2 the worst over EVERY graph on 4 vertices 63 graphs 2 the smallest graph attaining it the single edge 1-2 the largest graph attaining it 1-2, 1-3, 1-4, 2-3, 3-4 and the promise every graph, every size 2

The first row of the chain is an equality here, and that is the coincidence that makes this instance the worst case: the matching is not merely a lower bound on the optimum, it equals it. The cover is then twice the optimum exactly, with no slack anywhere in the chain.

The two witnesses from the sweep are both worth looking at. The single edge attains the ratio trivially — matching 1, cover 2, optimum 1 — and proves nothing about interesting graphs. The five-edge witness on four vertices is the same ratio on a graph that is nearly complete, and it is the one that shows the bound is not about degenerate cases. A page reporting only the first would be technically correct and would mislead.

For a faded rehearsal, move the slider to five vertices and predict the worst ratio before running it. The supplied first move: the proof gives 2 for every size, and a single edge is a graph on five vertices too, so the worst ratio cannot be below 2 and cannot be above it. Say how many graphs are searched, and then check — and note that the answer being the same at three, four and five vertices is still not the theorem.

Common mistakes

Reading a guarantee as a statement about the optimum“Within a factor 2 of optimal” is true and is proved without ever evaluating the optimum. If you cannot say which computable quantity the argument compares the answer to, you cannot check the guarantee and you cannot tell a proved bound from an observed one.

Quoting a realised ratio as the algorithm's ratioThis graph gives 2, the five-cycle gives 4/3 and the two triangles give 1. The promise is 2 for every graph and no single instance establishes it. The panel prints the instance's ratio, the worst over a whole size, and the promise as three separate rows for exactly this reason.

Approximating a problem on an instance where it is exactly solvableBipartite structure, bounded degree, tree shape: each turns this problem polynomial. Reaching for the 2-approximation without checking is how an algorithm returns twice the right answer on an instance that would have given the right answer cheaply, which is precisely what happens on the default graph here.

Check your understanding

✓

Finish when you can prove a ratio against a lower bound and print it with its optimum.

You should be able to construct a maximal matching by hand, show its endpoints cover the graph, prove the two inequalities that give the factor of 2, write the four-link chain and identify the only link mentioning the optimum, and name a special case where the exact answer is available in polynomial time.

Note: The lower bound here came from the algorithm's own run. “The Hypothesis Doing the Work” takes its lower bound from a minimum spanning tree instead, and the guarantee holds only under an assumption about the input that the panel lets you switch off.