An Approximate Solution to the Minimum Vertex Cover Problem: The Salvador Algorithm

Source abstract

The Minimum Vertex Cover problem is NP-hard. Its classical polynomial-time approximation ratio is ~2; under $\mathrm{P}\neq\mathrm{NP}$ no polynomial-time algorithm achieves $\sqrt{2}-\varepsilon$ for any fixed $\varepsilon>0$ (Khot–Minzer–Safra), and under the Unique Games Conjecture (UGC) not even $2-\varepsilon$ (Khot–Regev). We present FindVertexCover, a linear-time ensemble algorithm that computes nine independently valid vertex covers of the input graph $G=(V,E)$ and returns the smallest. Four of the candidates—and the redundant-vertex pruning pass applied to each—adapt the published Hvala ensemble, which proves an unconditional $O(n+m)$ time and space bound and a worst-case ratio at most 2, where $n=|V|$ and $m=|E|$; Salvador therefore contains Hvala and inherits its ratio-2 guarantee. Salvador adds a Min-to-Min heuristic, a primal-dual 2-approximation, a planar forest-core reduction to a weighted Minimum Independent Dominating Set gadget solved by a Baker-style pass, and, new in this version, two further candidates: (i)~the bipartite planar oriented-incidence reduction, whose auxiliary graph we prove is always a disjoint union of even cycles and single edges, so its minimum-weight vertex cover is computed \emph{exactly} by a linear-time cycle dynamic program; and (ii)~a budgeted (1,2)-swap iterated local search that improves the best cover found and stops after $O(n+m)$ work. The whole ensemble runs in worst-case $O(n+m)$ time and unconditionally achieves ratio at most 2. On the 68 DIMACS clique-complement instances of the NPBench collection, Salvador never returns a larger cover than Hvala: it is strictly smaller on 48 instances and equal on the other 20, with mean ratio 1.014 against 1.025. On a reproducible suite of 1746 graphs—1718 small graphs with exact optima, all solved optimally, and 28 large adversarial graphs with up to 200,000 vertices, whose ratios are certified by matching, clique-packing and spectral lower bounds—the ratio never exceeds 1.17. We conjecture a universal ratio of at most $7/5=\sqrt{2}-\varepsilon_0$ with $\varepsilon_0=\sqrt{2}-7/5>0$; by the Khot–Minzer–Safra theorem a proof of this conjecture would imply $\mathrm{P}=\mathrm{NP}$, and a proof of any constant ratio below 2 would refute UGC under $\mathrm{P}\neq\mathrm{NP}$. These consequences are conditional: the conjecture is supported by experiments, not proved. An open-source implementation is released as the Salvador package (v0.0.9).