Matpic
mathematics, in pictures
Concept

Vertex cover

A set of a graph's vertices that touches every edge. Finding the smallest is hard in general, and relaxing the choice of each vertex from yes-or-no to a fraction gives a linear programme whose answer is always within a factor of two.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

A matching of 4 and a cover of 4. A bipartite graph with its largest matching drawn thick and a smallest set of vertices meeting every edge ringed, the two having the same size.

What the search has when it fails

A largest matching is easy to find and hard to certify: the claim that nothing larger exists is a claim about every arrangement not tried. The certificate turns out to be free — it is the wreckage of the search that failed.

discrete · Halls theorem A relaxation that answers in halves. x = ½,½,½,½,½,1,0,0,½,½,½; LP 5; whole cover 6.

A relaxation that answers in halves

The cheapest set of points touching every edge of a graph is hard to find. Allow each point to be taken fractionally and the problem becomes a linear programme — and its best answers are never messier than halves. Every point gets 0, ½ or 1, the 0s and 1s can always be trusted, and the proof is a picture: double the graph into a bipartite one, where a matching decides everything exactly.

applied · Duality

Named alongside it

The objects these essays reach for when they reach for this one.

DualityMatchingApproximationBipartite graphCertificateCounting argumentDeficiencyExistence proofGraphLinear programmingRelaxation

All concepts