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, and Khot and Regev showed that, assuming the Unique Games Conjecture (UGC), no polynomial-time algorithm can achieve a factor $2-\varepsilon$ for any fixed $\varepsilon>0$. We present FindVertexCover, a linear-time ensemble algorithm that runs seven independently valid vertex-cover heuristics on the input graph $G=(V,E)$ and returns the smallest cover found, then prunes redundant vertices. Four of the seven candidates—and the final redundant-vertex pruning pass applied to each of them—adapt a published ensemble that proves an unconditional $O(n+m)$ time and space bound and a worst-case approximation ratio at most 2 for every graph, where $n=|V|$ and $m=|E|$. \textsc{Salvador} extends that ensemble with two further linear-time candidates of its own and a sixth candidate, SolveVC, that reduces $G$ to a linear-size planar forest core via a weighted Minimum Independent Dominating Set (MIDS) gadget and solves that gadget with an accuracy-controlled Baker-style PTAS whose layering width is $k=\lceil 1/\varepsilon\rceil$; non-core edges are covered by a greedy repair step. At the package default $\varepsilon=1$, the Baker layering width is $k=1$ and the PTAS pass degenerates to its linear-time greedy baseline, so every one of the seven candidates—and hence the ensemble as a whole—runs in worst-case $O(n+m)$ time; because one candidate is the classical maximal-matching heuristic, the ensemble unconditionally achieves approximation ratio at most 2 on every graph, a theorem rather than a conjecture. We conjecture a universal ratio bound $R^\star<2$ for the default call; on a reproducible suite of 1,746 test graphs, ranging from exhaustively enumerated small graphs to random and adversarial graphs with up to 200,000 vertices, the observed ratio never exceeds $1.61$, well below the classical $7/4$ mark. If a bound below 2 were proved for the ensemble, then, under the standard assumption $\mathrm{P}\neq\mathrm{NP}$, the Khot–Regev UGC-based hardness theorem for Vertex Cover would force the Unique Games Conjecture to be false. An open-source implementation is released as the Salvador package (v0.0.7).