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

Minimum Vertex Cover has a classical linear-time ratio of 2, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 2 unless $\mathrm{P}=\mathrm{NP}$. We present version 0.1.6 of Salvador, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in $O((n+m)\,\alpha(n))$ time, and that the returned cover has at most \(2\tau-r\) vertices, where $r$ is the number of components with an edge, so the ratio is at most 1.999999999 whenever $\tau\le10^{9}r$. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft–Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most $2L-|M|$ vertices, for a lower bound \(L\le\tau\) and the maximal matching $M$, is within ratio $3/2$ on that instance. In a reproducible suite the returned cover satisfies \(|C|\le2\tau-|M|\) on all 291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 68 DIMACS clique complements it is never worse than Hvala and optimal on 39 instances against 18. Whether \(|C|\le2\tau-|M|\) holds on every graph is stated as a conjecture: a proof would give a linear-time $3/2$-approximation and would refute the Unique Games Conjecture unless $\mathrm{P}=\mathrm{NP}$.

Authors

Publication Details

Journal
Preprints.org
Published
2026-11-18
DOI
https://doi.org/10.20944/preprints202605.2000.v9
Primary Topic
Complexity and Algorithms in Graphs
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

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

Frank Vega
Preprints.org
Complexity and Algorithms in Graphs
preprint

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

Frank Vega
preprint en

Abstract

Minimum Vertex Cover has a classical linear-time ratio of 2, and under the Unique Games Conjecture no polynomial-time algorithm achieves a fixed ratio below 2 unless $\mathrm{P}=\mathrm{NP}$. We present version 0.1.6 of Salvador, a linear-time ensemble of seventeen strategies, numbered in the order in which they are computed: twelve base strategies (component amplification before a maximal matching, the maximal matching itself, degree and weight heuristics, reductions to auxiliary problems that are solved exactly, a decomposition into bipartite layers, a weighted subdivision reduction and a bounded-treewidth dynamic program), followed by five improvers (a union pass, local search, reduce-and-search, consensus forcing and a swap-maximize refinement). We prove that every strategy runs in $O((n+m)\,\alpha(n))$ time, and that the returned cover has at most \(2\tau-r\) vertices, where $r$ is the number of components with an edge, so the ratio is at most 1.999999999 whenever $\tau\le10^{9}r$. We prove exactness or a bounded ratio on several classes of graphs, among them every bipartite graph on which the Hopcroft–Karp phases of the layer strategy reach a maximum matching, and we give a per-instance certificate: a cover with at most $2L-|M|$ vertices, for a lower bound \(L\le\tau\) and the maximal matching $M$, is within ratio $3/2$ on that instance. In a reproducible suite the returned cover satisfies \(|C|\le2\tau-|M|\) on all 291 tested graphs with a known optimum and is certified on the six without one, although single strategies violate it; on the 68 DIMACS clique complements it is never worse than Hvala and optimal on 39 instances against 18. Whether \(|C|\le2\tau-|M|\) holds on every graph is stated as a conjecture: a proof would give a linear-time $3/2$-approximation and would refute the Unique Games Conjecture unless $\mathrm{P}=\mathrm{NP}$.

Preprints.org
Complexity and Algorithms in Graphs
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon