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

Source abstract

The Minimum Vertex Cover problem is NP-hard. The best known polynomial-time approximation ratio is~$2$, matching a Unique Games Conjecture lower bound of~$2-\varepsilon$. Without the conjecture, a~$\sqrt{2}-\varepsilon$ inapproximability holds under $\mathrm{P}\neq\mathrm{NP}$ from $2$-to-$2$ games. We present \textsc{FindVertexCover}, an algorithm that reduces any graph to a linear-size planar core via a weighted Minimum Independent Dominating Set gadget and then applies a linear Baker-style pass. It runs in $O(n+m)$ time and returns a valid vertex cover. Experiments on $68$ NPBench clique-complement instances return a vertex cover at most $1.197$ times the reference optimum, with a mean ratio of $1.030$; the certified a posteriori upper bound derived from the NetworkX 2-approximation baseline is at most $1.986$. We conjecture that the approximation ratio is universally bounded by $1.4$. Crucially, $1.4 = \sqrt{2} - \varepsilon_0$ for $\varepsilon_0 = \sqrt{2} - \frac{7}{5} \approx 0.0142$, so proving the conjecture would place the algorithm strictly below the $\sqrt{2}$ inapproximability threshold and imply $\mathrm{P}=\mathrm{NP}$ directly and unconditionally. An open-source implementation is released as the Salvador package (v0.0.2).