A relaxation that answers in halves

A bound that may be off by a third and tours within half again of the best measured how far a linear programme can sit from the whole-number problem it relaxes, for the hardest problem those essays met, the shortest tour. The gap there was a fraction of the answer, and how large a fraction is still an open question. This essay takes a simpler hard problem, where the relaxation can be understood completely: not how far it is from the truth, but exactly what shape its answers have, and which parts of them are true.

The problem is vertex cover. Given a graph, choose as few points as possible so that every edge has at least one chosen end. It is one of Richard Karp’s twenty-one problems shown in 1972 to be as hard as any whose answers can be checked quickly, and no fast method for it is known. Its relaxation lets each point $v$ be chosen to an extent $x_v$ between 0 and 1, requires $x_u + x_v \ge 1$ for every edge, and minimises $\sum_v x_v$. That is a linear programme — the kind the simplex method walks from corner to corner, and the kind interior-point methods solve in polynomial time even where a squashed cube defeats the simplex — and its value is a lower bound for the cheapest cover, since every whole cover is one of the fractional ones. What does its optimum look like?

Only halves #

George Nemhauser and Leslie Trotter proved in 1974 that the relaxation always has an optimal solution in which every $x_v$ is 0, ½ or 1 — and more: every corner of its feasible region, every vertex of the polytope, has that form. The figure shows one on a graph built to need all three values. A pentagon and a triangle hang off a star. Each odd cycle takes ½ at every point, because an odd cycle cannot be covered by whole points without paying for more than half of them, while halves cover every edge exactly. The star’s centre takes 1 and two of its leaves take 0, because one point at the centre covers three edges at once. The relaxation’s value is 5, the cheapest whole cover has 6 points, and one cheapest cover takes the centre and leaves the leaves — exactly as the corner suggests.

That halves are enough is surprising against the background of where the corners stop being whole, which showed why bipartite structure makes a linear programme’s corners whole and an odd cycle breaks it. The odd cycle does break it, but only by one step: the corners become halves and nothing finer. The reason is a construction that turns any graph back into a bipartite one.

Doubling the graph #

Split each point $v$ of the graph into two copies, $v'$ on the left and $v''$ on the right, and replace each edge $uv$ by the two edges $u'v''$ and $v'u''$. The result is the bipartite double cover: twice as many points, twice as many edges, and no odd cycle anywhere, since every edge runs from left to right. For a pentagon it is a single cycle of length ten.

In a bipartite graph the cheapest cover is found exactly: by Kőnig’s theorem its size equals the size of the largest matching, and the alternating search that fails to enlarge a matching hands over a cover of the same size. Now take a cheapest cover of the double cover and give each original point $v$ the weight

$$x_v = \tfrac12\,\big(\text{number of } v', v'' \text{ in the cover}\big).$$

Every edge $uv$ of the original graph is covered, because the double-cover edges $u'v''$ and $v'u''$ are both covered, which needs at least two of the four copies, so $x_u + x_v \ge 1$. Conversely, any fractional cover $x$ of the original gives a fractional cover of the double cover, $x$ on both copies, of twice the value — and the double cover’s relaxation has whole corners. So the relaxation’s optimum is exactly half the double cover’s cheapest cover, it is attained by the halved cover, and that solution uses only 0, ½ and 1. For the pentagon the double cover’s largest matching has five edges, every pair of copies contributes one, and every point of the pentagon gets ½: a total of $2\tfrac12$ against the 3 whole points any cover of a pentagon needs.

That is the entire proof. It also shows why the relaxation can never be infeasible or unbounded, the cases when one of the two numbers is missing catalogued: taking every point at 1 is always feasible, and nothing is ever negative. Every figure here solves the relaxation that way — by one maximum matching on a bipartite graph twice the size — rather than by a general linear-programming method.

Every graph on six points #

The census takes all $2^{15} = 32{,}768$ ways of putting edges among six labelled points, solves the relaxation by the double cover, and finds the cheapest whole cover by trying every set of points. The relaxation’s value is always a multiple of a half — that is the theorem — and the whole cover is never below it and never more than twice it, because rounding every ½ up to 1 turns any half-integral corner into a whole cover of at most twice the cost.

On 73.8% of the graphs the relaxation is already exact. The rest sit just above the diagonal, mostly by half a point, and the worst ratio, $5/3$, belongs to a single graph: the complete graph on six points, whose relaxation is 3 — a half at every point — and whose cheapest cover needs 5. In general the complete graph on $n$ points has ratio $(n-1)/(n/2) = 2 - 2/n$, which climbs to 2. So rounding the relaxation is a factor-two approximation, and on complete graphs no better than that: the relaxation itself cannot certify anything closer.

The whole parts can be trusted #

The second half of Nemhauser and Trotter’s theorem is the useful one. If an optimal corner sets a point to 1, some cheapest whole cover contains it; if it sets a point to 0, some cheapest whole cover leaves it out. The relaxation’s whole parts are never misleading, and the whole-number problem reduces to the part where the relaxation said ½.

The figure checks this twice. On every one of the 32,768 six-point graphs, the half-integral corner from the double cover agrees with at least one cheapest cover on all of its 0s and 1s. On 300 random graphs with sixteen points, each point is settled at 0 or 1 whenever doing so leaves the relaxation’s optimum unchanged — the points with a single neighbour first, by taking their neighbour — and then the unsettled remainder is covered exactly by search; the total always equals the cheapest whole cover, with no exception.

Why the whole parts persist has a short argument, and it is a matching argument again. Let $S$ be the points the corner sets to 1 and $Z$ the points it sets to 0. No edge joins two points of $Z$, since their weights would sum to nought, so every neighbour of a point in $Z$ lies in $S$ — a point of $Z$ next to a point at ½ would leave that edge short. Now the optimality of the corner forces a structure between them: there is a matching that pairs every point of $S$ with a distinct point of $Z$. If there were not, Hall’s condition would fail for some set of points in $S$ with too few neighbours in $Z$, and lowering those points from 1 to ½ while raising their neighbours in $Z$ from 0 to ½ would make the cover cheaper, which the optimum forbids. Given the matching, any whole cover must spend at least $|S|$ points on the edges between $S$ and $Z$, one for each matched edge, and the set $S$ itself covers all of them and every edge out of $Z$. So swapping whatever a cheapest cover does on $S \cup Z$ for exactly $S$ costs nothing, and the cover that results takes all of $S$ and none of $Z$. This configuration — an independent set $Z$ whose neighbours $S$ can be matched into it — is called a crown, and removing crowns is how the kernel is found.

How much is settled varies enormously, and the bars show it. On 125 of the 300 graphs the relaxation settles all sixteen points and the problem is solved outright. On 79 it settles nothing: every optimal corner is ½ everywhere, the relaxation says only that the answer lies between eight and sixteen, and the hard problem is the whole graph. This is the basis of a standard method in parameterised algorithms: the unsettled core has at most twice as many points as the relaxation’s value, so any instance can be shrunk, in polynomial time, to a kernel of at most $2k$ points for a cover of size $k$, and only the kernel needs exhaustive search.

The matching on the other side #

Every linear programme has a dual that has to meet it, and the dual of the vertex-cover relaxation is the fractional matching: give each edge a weight $y_e \ge 0$ so that the weights meeting at any point add to at most 1, and make the total as large as possible. Any fractional matching bounds any fractional cover from below, since each edge’s weight is paid for by its two ends; the duality theorem says the best of each meet.

The double cover produces the dual too. Its largest matching uses, for each original edge, zero, one or both of the two copies, and halving those counts gives a fractional matching of the original graph whose weights are again 0, ½ and 1. On the hero graph the odd cycles carry ½ on every edge — five halves around the pentagon, three around the triangle — and the star sends 1 down a single edge. The total is 5, equal to the relaxation’s value, and the two certificates prove each other optimal. They also explain each other: an odd cycle with ½ on every edge is a fractional matching that no whole matching can imitate, which is exactly why its points must take ½ in the cover. The price on a constraint is, here, the share of a point’s cover that each edge is responsible for.

Matchings bound covers from both sides #

There is a cruder version of the same factor of two that needs no linear programme. Any matching — a set of edges no two sharing a point — needs a separate cover point for each of its edges, so the cheapest cover is at least the size of the largest matching. And a maximal matching, one that cannot be extended, has the opposite property: taking both ends of every edge in it covers the whole graph, since an uncovered edge could have been added to the matching. So a matching found greedily, edge by edge, gives a cover at most twice the cheapest, in a single pass over the edges. In a bipartite graph the two sides meet exactly, which is Kőnig’s theorem; in a general graph they can differ by a factor of two, and the complete graph is again the worst case, with matchings of size $n/2$ against covers of size $n - 1$.

The relaxation sits between those two whole-number bounds, and the fractional matching sits with it: largest whole matching $\le$ largest fractional matching $=$ relaxation $\le$ cheapest whole cover. The two middle quantities are equal by duality and half-integral by the double cover, and the outer two are the problems people actually want solved. Jack Edmonds showed in 1965 that the largest whole matching can be found in polynomial time even in non-bipartite graphs, by shrinking odd cycles — the very cycles that force halves here — so the left end of the chain is easy and the right end is hard, with the relaxation in between telling exactly how much the odd cycles matter.

Random graphs, sparse and dense #

On random graphs the relaxation’s behaviour changes with density. The figure takes graphs on sixty points with average degree $c$ from a half to five, twenty at each density, finds the cheapest cover by branching and the relaxation by the double cover. For sparse graphs the two agree, or nearly — at $c = 1$ the cheapest cover is 26.9% of the points and the relaxation 26.8% — and the relaxation settles almost every point: a sparse random graph is mostly trees hanging off small pieces, and repeatedly taking the neighbour of a point with one edge covers it. Richard Karp and Michael Sipser analysed exactly that leaf-removal process in 1981 and found that on large random graphs it clears everything but a vanishing part while $c < e$, and leaves a core of linear size once $c > e$.

The figure shows the same change, smeared by the small size. The unsettled core is under 3% up to $c = 2$, 18% at $c = e$, and 91% at $c = 5$, where the relaxation is stuck at almost exactly half the points while the true cover keeps growing — 57% at $c = 5$. The relaxation’s half-integral corner on a dense random graph is nearly all halves, which certifies only that the answer lies between $n/2$ and $n$, and the gap between the two curves is the part of the problem the relaxation cannot see. Where the moment everything joins up found a giant component appearing at $c = 1$, the cover problem has its own threshold at $c = e$, and it is the core, not the giant, that makes it hard.

What the computations show and assume #

The relaxation is solved exactly in every figure, by a maximum matching in the double cover, and every solution is checked to cover every edge with weights summing to at least 1. The cheapest whole covers are exact: by trying every set on six points, and by branching on a point of largest degree for sixteen and sixty points. The census is exhaustive over labelled graphs, so isomorphic graphs are counted many times; the shares in it are shares of labelled graphs, which weights symmetric graphs less than asymmetric ones.

The settling procedure on random graphs fixes one point at a time whenever the relaxation’s optimum does not change. That finds a maximal set of settled points, not necessarily the theoretical minimum core; the core reported is an upper bound on the points every optimal corner leaves at ½. And the random-graph figure is at sixty points, where the threshold at $e$ is a gentle bend rather than the sharp change Karp and Sipser’s analysis describes in the limit.

Still open: whether two is the best factor #

Rounding the relaxation gives a factor of two, and nobody knows how to do fundamentally better. Irit Dinur and Samuel Safra proved in 2005 that no polynomial method can guarantee a factor below 1.36 unless P = NP, and Subhash Khot, Dor Minzer and Muli Safra raised that to $\sqrt 2$ in 2018. If the Unique Games Conjecture is true, no polynomial method can guarantee any factor below 2 — Khot and Oded Regev proved that in 2008 — and the half-integral relaxation, with its trivial rounding, would be the best possible algorithm. The conjecture is open, and with it the question of whether the gap between $\sqrt 2$ and 2 is real.

The relaxation has been strengthened in every way anybody could think of — adding constraints for odd cycles, cliques, and whole hierarchies of lifted inequalities — and on worst-case graphs each strengthening still leaves a gap approaching 2. Whether some polynomial-size relaxation does better, or whether the factor two is a wall, is one of the cleanest open questions about what linear programmes can certify.

Halves and a picture #

The vertex-cover relaxation’s best answers are made of 0, ½ and 1, because doubling the graph into a bipartite one turns it into a problem a matching solves exactly; and the 0s and 1s can always be trusted. On every six-point graph and on hundreds of random ones the persistence holds, the relaxation is exact on nearly three quarters of the small graphs and off by at most a factor approaching two on complete ones, and its dual is a fractional matching of halves read off the same double cover. Where the relaxation settles everything the problem is easy; where it answers ½ everywhere — on odd cycles, cliques and the dense core of random graphs — the hard part of an NP-complete problem is exactly what is left.