Salvador: An Approximate Solution to the Minimum Vertex Cover Problem

Source abstract

Minimum Vertex Cover has a classical polynomial-time ratio of 2, and a manuscript released by the OpenAI Math Team in October 2026, not yet peer reviewed, reports a proof of the Unique Games Conjecture in the form that, by the theorem of Khot and Regev, makes every fixed ratio below 2 NP-hard. We present SALVADOR (v0.1.1), a worst-case O(n + m) ensemble of eleven candidate covers plus a swap-maximize refinement; it contains the Hvala ensemble, so it is valid and has ratio at most 2 on every graph. We analyse each strategy c1, . . . , c12 separately and prove what it guarantees: c4 is exact on forests, cycles and complete graphs, and c4 and c8 are exact on every bipartite graph whose components are regular or degree-separated, which includes all regular bipartite graphs of every degree; c8 meets the Caro–Wei bound on every graph; c1, c5 have ratio 2ν/τ; c2 has ratio 11/6 on subcubic graphs; c3 beats 2 on hub-dominated graphs; c10 solves a labelled, weighted edge-dominating-set gadget whose optimum is a minimum vertex cover with the fewest doubly covered edges, by a dynamic program whose bags never exceed six nodes; c11 is exact when its elimination core is empty; and c9, c12 never worsen the best cover. Combining these certificates, SALVADOR has ratio at most 1.999999999 on every graph outside a residue R of nearly K˝onig–Egerváry graphs. We then explain why the ensemble succeeds on R: every cover satisfies the exact identity |C| = |y| + y(E(C)) + defy(C) for every fractional matching y, so on R the excess of a cover is its violation of complementary slackness, and the a-posteriori certificate |C|/νf equals the true ratio up to a factor 1 + 5 · 10−10; the strategies keep this violation small, and on regular graphs it is exactly the number of doubly covered edges, the quantity that c10 minimises. Experimentally, on 1,744 benchmark graphs, 152 bipartite graphs, 117 Khot–Regev YES instances, 120 mechanism instances and 267 regular graphs of degree up to 64, every instance carries a per-instance certificate of ratio at most 1.237, the ratio never exceeds 1.0455 on bipartite graphs and 1.0425 on YES instances with known optimum, all 117 regular bipartite graphs are solved exactly, and the bags of c10 never exceed six nodes. If the reported hardness holds, a proof that SALVADOR achieves 2 − ε0 on all of R would imply P = NP; we state this as a conditional theorem, not as a result.